## 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 Zn when 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:

Conjecture 2: If GCD(2,n) = 1 and n = p*q where p and q are distinct primes then 2φ(n)/2 = 1 and all integers up to 2φ(n)/2 are distinct.

To find φ(n) when n is the product of two distinct primes, one must simply compute 2 to an incremental power x until it reaches 1, at which point it should stop and spit out the index of x, and since the index at  x=φ(n)/2 then φ(n) = 2x

And this conjecture if false will make the following algorithm go into an infinite loop. Just kidding. I'm confident that it will always work as long as the input n is greater than 4, is not a prime, or a prime power, or twice a prime power.

Unfortunately,  Conjecture 2 turns out to be false. In particular, 2φ(n)/2 = 1 is correct but φ(n)/2 may not be the smallest integer that produces 1;  the function below will find the order of a mod n but the order may be smaller than φ(n)/2. However, I still boldly predict that there must be an element a mod n such that if GCD(a,n) = 1 and n = p*q where p and q are distinct primes then aφ(n)/2 = 1 and all integers up to aφ(n)/2 are distinct for all n when n is composed of two distinct primes where each one is greater than 2.
``````

/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
---------------------------------------------------- */
function findOrder(a,n)
{
int a = 2;
int i = 1;
while (a != 1)
{
i++;
a = n % (a^i);
}
return i;
}
``````
` `
``````function findOrder(a,n)
{

var i = 1;

while(a !== 1)
{
i = i + 1;
a = Math.pow(2, i);
a = a % n;
}
return i;
}``````

But here is a revised version of the algorithm that splits n in half and goes backwards as opposed to forwards, which is guaranteed to hit φ(n)/2 since φ(n)/2 is strictly smaller than n/2.

In Javascript.

``````
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
---------------------------------------------------- */
function findPhi(n)
{
var a = 2;
var i = Math.floor(n/2);

while(a !== 1 && i > 0)
{
i = i - 1;
a = (Math.pow(2, i)) % n;
}
return 2*i;
}``````

Of course, according to Javascript's Math.pow anything above 22000 is equal to Infinity, so if the input n is anything above, say around 4000, findPhi may graciously return φ(n)/3, φ(n)/4, or φ(n)/5, or φ(n)/10, or whatever multiple of φ(n) it decides is appropriate.

A better algorithm for modular exponentiation includes expressing the exponent i of a in binary notation, and then by successively squaring and reducing modulo n the least positive residues of a, a2, a4,..., a2k mod n can be found, and from there the least positive residues mod n of a2j must be multiplied for those j that correspond to 1 in the binary notation of the exponent, while reducing mod n after each multiplication.

Theorem: The algorithm for modular exponentiation described above would run in

O((log2n)2 log2i)

bit operations where n is the product of two distinct primes p and q both greater than 2, a is an integer strictly smaller than n, and i is some large exponent of a.

Proof: See pages 148 - 149 from Elementary Number Theory, by Kenneth H. Rosen. In particular, Theorem 4.9 on page 148.

References:
Hungerford Thomas W., Abstract Algebra, 2006
Rosen, Kenneth H., Elementary Number Theory, 2005