As we saw in the previous section, the elements of Z_n which generate all of Z_n are exacly those for elements for which gcd(k,n)=1. Also we mentioned that we also have a notion of multiplicaton in Z_n.

Now we wish to find which elements in Z_n have a multiplicative inverse. Suppose a is in Z_n, does there exist an element c in Z_n such that a*c=1 in Z_n. If the answer is yes then we say that a is in Z_n^*. It is easy to see that if gcd(a,n)=1 then a is in Z_n^*. Because, if gcd(a,n)=1, then a generates all of Z_n. Especially, there is a c such that c*a=1 in Z_n. Now if gcd(a,n) is not one, then it does not generate all of Z_n and thus there can be no element c in Z_n such that c*a=1 in Z_n, for if there were then a would generate the entire group (which is a contradiction). Thus we see that

Z_n^*={ a in Z_n such that there exist an element c in Z_n with a*c=1}
={a in Z_n such that gcd(a,n)=1}

Now from this we can see that the number of elements in Z_n^* is exactly φ(n) from our previous lesson. That is in Z_n there exactly φ(n) elements that have multiplicative inverses. Notice that if we are looking at Z_p were p is prime then the number of elements in Z_p^* is φ(p)=p-1. So this tells us that every element of Z_p (with the exception of 0) has a multiplicative inverse.

Problem Set 7 :

List the elements of Z₉^*.
Check to make sure you have all of them by computing φ(9).
Find the multiplicative inverses of each of these elements.

Prove that if a and b are both in Z_n^*, then a*b is in Z_n^*.

Prove that if a is in Z_n (for n>1), then a is in Z_n^* if and only if gcd(a,n)=1 using only the fact from lesson 1 that gcd(a,n) is the smallest possible positive integer of the form as+nt.

End of Problem Set 7

These notions discussed in the previous section all play a fundamental role in the development and implementation of the RSA algorithm (which will be our final topic, and is where we actually talk about cryptography).

One other topic that is important to discuss is finding large primes or checking if large numbers are indeed primes.

First we would like to construct a list of prime numbers. To do so, suppose we only start with the knowledge that 2 is prime. Using the Fundamental Theorem of Arithmetic any number n may be written as a product of distinct prime with powers on the primes (uniquely, up to reordering of the primes) as

n=p₁^k₁p₂^k₂***p_s-1^k_s-1p_s^k_s

So to check that n is prime we must only make sure that it is not divisible by any primes less than n (or equivalently that n is not 0 (mod p) for any prime less that n)

So now is 3 prime, well 3 mod 2=1 so 3 is also prime.

What about 4, well since 3 mod 2=1, and we added 1 to 3, 4 mod 2 =0 so no 4 is not prime.

For 5, 5mod 2=1 and 5mod 3=2 so five is prime, but we need not check if 5+1 is prime since 5+1mod2=0 and 5+1mod3=0.

For 7, 7mod2=1,7mod3=1,7mod5=2. So 7 is prime and we need not check if any of 7 + (1,2, or 3) are prime because adding 1,2,3 respectively give us that 7+1mod2=0,7+2mod3=0,7+3mod5=0, giving us that 8,9,10 are not prime (since adding the additive inverse in Z₂, Z₃, Z₅ gives us a number with modp=0 for some p).

For 11, 11mod2=1,11mod3=2,11mod5=1,11mod7=4. So 11 is a prime and we need not check if any of 11+(1,1,4,3) are prime since adding any of these would give us 0 modp for some p less than n.

Now since we need not check 12,14,15 we still need to check 13.... and we continue to do so in the same way as we have.

And continue to construct this list adding one prime at a time. Until you get a large number of primes. Now suppose that we have some large n and we want to see if n is prime or some number close to n is prime. We can check to see if n is prime by reducing it mod p for every p less than n (actually we can stop at any p that is less than n^1/2, since if any p larger than this divides n some prime smaller than n^1/2 also does and we are just wasting computation time). Now compute the following (list the know primes up to and including n^1/2, that were computed before, in ascending order p₁, p₂,p₃,...,p_k)

n modp₁=n₁
n modp₂=n₂
n modp₃=n₃
.
.
.
n modp_k=n_k

If any of these are 0, then n is not prime otherwise n is prime. Either way we now know that we need not test worry about testing any of the numbers

n + p₁-n₁
n + p₁-n₁
n + p₁-n₁
.
.
.
n + p₁-n₁

since all of these will give us numbers reduce mod p_i to 0, for at least one i between 1 and k, hence are not prime. Also, any integer multiple of p_i may be added to n + p_i-n_i
to get another composite number for the same reason


Example: Lets do this for n=183, since 191^1/2 < 14. We only need to use primes < 14 (which we already found 2,3,5,7,11,13)

191mod2=1
191mod3=2
191mod5=1
191mod7=6
191mod11=4
191mod13=9

So we see that 191 is prime, and we also see that 192(also any even),192(plus any multiple of 3),195(plus any multiple of 5),192(plus any multiple of 7),198(plus any multiple of 11),195(plus any multiple of 13) are not prime. This sounds arbitrary but when implemented into a well constructed program can be useful to speed up the process of finding large prime numbers.

To read more on other (and more efficient) ways of finding primes and proving primality see Finding Primes and Proving Primality.

Problem Set 8 :

Implement this algorithm by hand for n= 1121. Is 1121 prime? What numbers can you conclude are not prime around 1121?

Challenge: Write a computer program (using some language you know, I prefer C) to find all primes less that one billion.

End of Problem Set 8

References and Further Reading:
[1]David S. Dummit and Richard M. Foote Abstract Algebra 2nd Edition Prentice-Hall, Inc., 1999.
[2]Finding Primes and Proving Primality.