# Homework Help: Number theory - rings

Tags:
1. Sep 13, 2016

### 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?

2. Sep 13, 2016

### 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?

3. Sep 13, 2016

### micromass

Never mind, I'm an idiot.

Last edited: Sep 13, 2016
4. Sep 13, 2016

### SammyS

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

5. Sep 13, 2016

### SammyS

Staff Emeritus
What are the prime factors of 12?

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

6. Sep 13, 2016

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

7. Sep 13, 2016

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

8. Sep 13, 2016

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

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