Number Theory and Cryptography

III. Zn and Euler Phi-function




In Cryptography Lesson 2 we learned about Modular Arithmetic. When discussing integers mod n we are discussing the "group" Zn. When we write a=b (mod n) we say that a is congruent to b mod n. By this we of course mean a (mod n) = b(mod n). For example: 7=19(mod 12).


Zn is the set of all congruence classes. Meaning, any two integers a and b are in the same congruence class if a=b(mod n). But, how many congruence classes are there in Zn? Well how many possible remainders can you get when you divide by n? You can get 0,1,2,3,...,n-2,n-1, so exactly n!


Now how do we add in Zn? Consider as an example Z12. 9+5=2 (mod 12), so we say that in Z12 9+5=2. This works exactly like the calender if we start in the month of September and add five months we arrive in February, i.e. 9+5=2. So addition in Zn for arbitrary n means that we add the two numbers and reduce mod n. Similarly we can multiply in Zn. If we are working in Z12, 9*5=9 (mod 12). This also gives us the rule that was mentioned in the section on modular arithmetic, namely a*b (mod n)= (a (mod n))*(b (mod n)) (mod n).


Now what if in our example we had taken 21 instead of 9, since 21=9 (mod n) and -7 instead of 5, since -7=5 (mod n). Let's do the addition again 21+ (-7) = 2 (mod 12) and using the properties of modular arithmetic we can see that we have the option of replacing 9 with any integer a and 5 with any integer b, as long as 9=a (mod 12) and 5=b (mod 12) and we will get the same answer every time. It is for this reason we call any integer a such that 9=a (mod 12) representative for 9, since we have freedom in choosing it and we get the same results. Clearly the most obvious representative for 9 is 9 itself. Also, it should be mentioned that the multiplication of two numbers in Zn does not depend on the choice of representative for those numbers. Since we have this freedom to choose any representative for the numbers that we add and multiply in Zn, we say that addition and multiplication is well defined.


Now starting with an element of Zn, can we continue to add this element to itself repeatedly and get all element of Zn? Let's try with 9 in Z12.

So we start with 9
then 9+9=6 (mod 12)
then 9+9+9=3 (mod 12)
then 9+9+9+9=0 (mod 12)
and we see that if we continue to do this we can only arrive at either 0,3,6,9, but this is not all of Z12.

Now lets try the same thing with 5.
5+5=10 (mod 12), 5+5+5=3 (mod 12), 5+5+5+5=8 (mod 12), 5+5+5+5+5=1 (mod 12), 6*5=6 (mod 12), 7*5=11 (mod 12), 8*5=4 (mod 12), 9*5=9 (mod 12), 10*5=2 (mod 12), 11*5=7 (mod 12), 12*5=0 (mod 12). So from 5 we can arrive at any possible congruence class of Z12, namely 0,1,2,3,...,10,11.

So from 9 we can only arrive at {0,3,6,9}, but from 5 we can get any of {0,1,2,3,...,10,11}. We denote these possibilities as <5> and <9> and call them the subgroups of Z12 generated by 5 (and 9 respectively). Now why is it that <9> only has 4 members and <5> has all 12 members of Z12? This is because 9 is not relatively prime to 12 (gcd(3,12)=3) and 5 is relatively prime to 12 (gcd(5,12)). In fact if we want to find an element of Zn that generates all of Zn, we need only find a number k such that gcd(k,n)=1 (k that is relatively prime to n).


Problem Set 5 :

Using the properties of Z9. Show that if we write a positive integer a as a=an10n+an-110n-1+...+a110+a0, then a=an+an-1+...+a1+a0 (mod 9). Compare this to the typical arithmetic rule that a number is divisible by 9 if and only if the sum of it's digits is 0.

How many elements of Z12 generate the entire group?

End of Problem Set 5



In the previous question you were ask to find how many elements of Z12 generate all of Z12, or equivalently how many numbers between 0 and 11 are relatively prime to 12. For such a small number it is easy to check each possibility and see which ones work. Now what if you were ask to do the same for an arbitrary n? This could be quite difficult if n were say 100,000,000,000. However there is a much much easier way to do this, and it involves using the Euler φ-function (this is the greek letter phi, pronounced the same as fee).


Euler φ-function: For any positive integer n, let φ(n) be the number of positive integers a with a relatively prime to n. As in our example φ(12)=4. For primes p, φ(p)=p-1, since every positive integer less than a prime is relatively prime to p. Now we have the following properties for φ(n).

For k a positive integer, and p prime, we have the formula

φ(pk)=pk-1(p-1)

The function φ is multiplicative meaning

φ(ab)=φ(a)φ(b) if gcd(a,b)=1


Recall now, from Cryptography Lesson 2, the Fundamental Theorem of Arithmetic, which tells us that every positive integer is uniquely a product of prime numbers. Meaning for positive integer n we can find distinct primes p1,p2,...,ps-1,ps and positive integers k1,k2,...,ks-1,ks to be able to write (uniquely)
n=p1k1p2k2***ps-1ks-1psks

Since any two distinct primes are relatively prime to each other and we have the second property, we get that

φ(n)=φ(p1k1)φ(p2k2)***φ(ps-1ks-1)φ(psks)

Then from the first property of φ(n) if follows that

φ(n)=p1k1-1(p1-1)p2k2-1(p2-1)***psks-1(ps-1)



Now we can use this function to easily answer the question; How many elements of Z12 generate the entire group? The answer is then φ(12)=φ(22*3)=2(2-1)30(3-1)=4. we can now even answer what seemed like it would take a long long time to figure out (even with a computer). How many numbers are relatively prime to 100,000,000,000 (and less than it)? Well...

100,000,000,000= (10)11= 211511

So φ(100,000,000,000)=210(2-1)510(5-1)=4*1010


Meaning there are exactly 40 Billion numbers relatively prime to 100,000,000,000. Also meaning that Z100,000,000,000 has 40 Billion generators.


Problem Set 6 :

Compute φ(43), φ(100), φ(455).

Prove the first property of φ(n), namely
for k a positive integer, and p prime, the equality

φ(pk)=pk-1(p-1) holds.


End of Problem Set 6


References and Further Reading:
[1]Joseph A. Gallian.Contemporary Abstract Algebra 4th Edition Houghton Mifflin Company, 1998.
[2]David S. Dummit and Richard M. Foote Abstract Algebra 2nd Edition Prentice-Hall, Inc., 1999.