1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number theory - rings

Tags:
  1. Sep 13, 2016 #1

    Rectifier

    User Avatar
    Gold Member

    The problem
    Consider the ring ##(Z_{12}, \otimes, \oplus)##

    Find all units.

    The attempt
    I know that I am supposed to find units u such that ##gcd(12,u)=1##

    But how do I do it the easiest way? I am not very keen to draw a multiplication table, calculate the terms and search where the multiplicative products are ##1##. I am neither interested in trying each value for ##u## from ##0## to ##11## and plop them inside the expression above and calculate the ##gcd## (to see if it matches ##1##) for every case using the Euclid's algorithm.

    Any suggestions?
     
  2. jcsd
  3. Sep 13, 2016 #2

    Rectifier

    User Avatar
    Gold Member

    Looks like i am just looking for the primes in the range ]0,12[ thus
    1, 3, 5, 7, 11 should seal the deal, right?
     
  4. Sep 13, 2016 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Never mind, I'm an idiot.
     
    Last edited: Sep 13, 2016
  5. Sep 13, 2016 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Actually, 3 is not relatively prime to 12. Also, 2 is a prime, but not in your list, and rightfully so.

    ... And by the way; 1 is not a prime, but yes, gcd(12, 1) = 1 .
     
  6. Sep 13, 2016 #5

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    What are the prime factors of 12?

    Choose numbers which do not have any of those as prime factors.
     
  7. Sep 13, 2016 #6

    fresh_42

    Staff: Mentor

    You are asking for a simple method, where you plug in a number ##n##, say ##n=2650755587110239046731## and all ##u## with ##gcd(n,u)=1## pop out. The only way to do it, is to write a program that does it. But even with such a program you will get into (time) trouble for really big ##n##. Given a candidate ##u##, say ##u=35946720007965521## the Euclidean algorithm is the way to find out, whether ##u## is invertible in ##\mathbb{Z}_n##. And it is a fast algorithm.
     
  8. Sep 13, 2016 #7
    For homework help and the general learning experience, try to include the definitions of the terms you are working with. This is beneficial to those helping you, but also the more often you state the definition, the more likely you will remember it for a test or project.

    Regarding the "easist way". Note that if you write down the definition of a unit, the multiplicative inverse of the unit is also a unit. (WHY?) That should cut your work in half.
     
  9. Sep 13, 2016 #8

    rcgldr

    User Avatar
    Homework Helper

    You're looking for numbers that are co-prime to 12, including 1. This leaves you with the set 1, 5, 7, 11.

    http://en.wikipedia.org/wiki/Unit_(ring_theory)

    Finding the prime factors of a large number n is time consuming, but should be faster than searching for all numbers i for 2 to n-1 where gcd(n,i) = 1 via Euclid method.

    Worst case for Euclidean algorithm are two successive Fibonacci numbers, fib(i), fib(i+1), which will take i-1 iterations. If u is large, it will take u x L iterations to find all the "units", where L is average the number of iterations to find gcd(u, i) (for i = 2 to u-1).

    Note that inverse of 5 mod 12 is 5, 7 mod 12 is 7, 11 mod 12 is 11, so it doesn't always cut your work in half.
     
    Last edited: Sep 13, 2016
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Number theory - rings
  1. Number Theory (Replies: 3)

  2. Number Theory (Replies: 1)

  3. Number Theory (Replies: 2)

  4. Number Theory (Replies: 7)

  5. Number of theory (Replies: 1)

Loading...