11.11.14

Finding Phi

Euler's phi function, namely φ(n), pops up in many odd places even though φ(n) is always even. 

Definition 1: φ(n) is the number of integers smaller than n that are relatively prime, or coprime to n. [Page 227 from Elementary Number Theory, by Kenneth H. Rosen.]


Theorem 00: If n is the product of two distinct primes p and q, then 

φ(n) = (p-1)(q-1). 

Proof: If n is the product of two distinct primes p and q then φ(n) = (p-1)(q-1) because for any prime p its greatest common divisor GCD with any integer other than itself is 1, therefore  the number of integers coprime with p is p-1. So if p and q are prime integers, then:


φ(p)*φ(q) = (p-1)(q-1) = φ(n)


Question: Is it possible to find φ(n) without factoring n to find the values of p and q?




The answer is yes and the next paragraphs explain why and how to obtain the value of φ(n) without factoring n.

Theorem 0φ(n) is even when n = p*q where p and q are 2 distinct prime integers.

Proof: All prime integers greater than 2 are odd since by definition of an even integer e, e is 2 times some other integer, namely  e = 2k for some positive integer k in Z, 
therefore e is divisible by 2 and yet a prime integer is only divisible by itself and 1.

Therefore, all primes greater than 2 are odd and by definition an odd integer is an even integer plus one, so if p is prime then p = 2v + 1 for some v in Z and since p-1 = (2v+1)-1=2v then for all primes p, p-1 is an even integer. (p-1)(q-1) is also even since say for some primes p, q  p-1 = 2r for some r in Z and q-1 = 2s for some s in Z. Therefore,


 (p-1)(q-1) = 2r2s = 4rs = 2(2rs) 

and since 2,r,s are all integers in Z, which is closed with respect to multiplication, then their product is also an integer in Z. Therefore, (p-1)(q-1) is an even integer. Therefore φ(n) is even when n = p*q where p & q are prime integers .'.

Since φ(n) is even when n is the product of 2 primes, then φ(n)/2 is a whole integer as well.

Euler also came up with the term primitive root to describe integers whose order is exactly φ(n). The order of an integer mod n is by definition:

Definition 2: The order of an element a in Zis the smallest integer k such that ak= 1 mod n. [Page 334 from Elementary Number Theory, by Kenneth H. Rosen.]

Euler correctly saw and proved that: 

aφ(n) = 1 mod n for any a co-prime with n. 

Euler also came up with the term primitive root, which he defined as:

Definition 3: If r and n are relatively prime (co-prime) integers with n > 0 and if the order of r mod n is equal to φ(n) then r is called a primitive root modulo n. [Page 336 from Elementary Number Theory, by Kenneth H. Rosen.]

Euler also correctly saw that every prime has a primitive root but his proof for this was incorrect. Lagrange provided the correct proof years later and in fact it can be shown that:

Theorem 1: A positive integer n has a primitive root if and only if it is of the form 2, 4, pt, or 2p where p is prime and t is a positive integer in Z.

Proof:  See pages 351 to 353 from Elementary Number Theory, by Kenneth H. Rosen. In particular, Theorem 9.15 from chapter 9.3: The Existence of Primitive Roots


Example 1: Below are a few examples of exponentiation tables in  Zn, which among other things reveal the order of elements that are co-prime with n. When n is 6  by Theorem 1 it must have a primitive root because it is of the form 2 times 3. The exponentiation table for Z6 reveals that 5 is a primitive root of 6 because 52 = 1 mod 6 and φ(6)=(3-1)(2-1)=2. Similarly, 10 = 2*5 so by Theorem 1 it should have a primitive root as it does.  


An exponentiation table to find orders of elements in Zwhen n is equal to 6 or 10


Example 2: When n is the product of two distinct primes both greater than 2, then by Theorem 1. n will not have any primitive roots as is shown in the table for Z35 when n = 5*7. In this case φ(35) = (5-1)*(7-1) = 24 but the smallest integer k such that ak= 1 mod 35 for any a in Z35 is 12, which is half of φ(35).


An exponentiation table to find orders of elements in Z35

The implications of this wicked construct, the grupoid  Zn under exponentiation, are not immediately obvious unless you are hunting for φ(n). 

Claim 1: The order of any element co-prime with n in the group Zn under multiplication when n is the product of two distinct primes p and q where p >2 and q >2 divides φ(n)/2

Proof:  Suppose that φ(n) is the smallest integer such that



aφ(n) = 1 mod n 

for any a relatively prime to n when n is the product of two distinct primes p and q where p >2 and q >2

The order of the group composed of all integers co-prime with n when n is the product of two distinct primes greater than 2 is φ(n) and for every element a relatively prime to n if has order k, then by Lagrange's Theorem the order of a divides the order of the group , namely k divides φ(n). Since it was assumed that φ(n) is the smallest integer such that  aφ(n) = 1 mod n  then k must be equal to φ(n).

However since n=p*q for some primes p and q both both greater than 2, then n does not have any primitive roots.  [See pages 351 to 353 from Elementary Number Theory, by Kenneth H. Rosen. In particular, Theorem 9.15 from chapter 9.3: The Existence of Primitive Roots]


In other words, the group composed of all integers co-prime with n does not have any elements a relatively prime to n, whose order equals φ(n).Therefore, φ(n) is not the smallest integer such that  aφ(n) = 1 for any a relatively prime to n when n is the product of two distinct primes p and q where p >2 and q >2.

Therefore, the maximum order than an element of the group composed of all integers co-prime with n when n is the product of 2 distinct odd primes can have is φ(n)/2  since 2 is the smallest integer > 1 to divide φ(n), which by Theorem 0 is an even integer.'.

Finally Finding Phi

To find φ(n), one must find which are the elements with the maximum order. 

Note that by Theorem 1: 
2 times any prime always has a primitive root yet if 2 does not divide n and n is the product of 2 primes p , q > 2 and p is not equal to 2 then the following conjecture arises: