Efficient Method for Finding Units in Number Theory Rings (Z12, ⊗, ⊕)

[Rectifier]

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?

 

[Rectifier]

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?

 

[micromass]

Never mind, I'm an idiot.

 

[SammyS]

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?

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 .

 

[SammyS]

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?

What are the prime factors of 12?

Choose numbers which do not have any of those as prime factors.

 

[fresh_42]

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.

 

[thelema418]

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.

 

[rcgldr]

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.

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.

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 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.

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.