**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)

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 Z

_{n }is

**the smallest integer k**such that a

^{k}= 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, p

^{t}, or 2p

^{t }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 Z

_{n}, 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 Z

_{6}reveals that 5 is a primitive root of 6 because 5

^{2}= 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 Z_{n }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 Z

_{35}when n = 5*7. In this case φ(35) = (5-1)*(7-1) = 24 but the smallest integer k such that a

^{k}= 1 mod 35 for any a in Z

_{35}is 12, which is half of φ(35).

An exponentiation table to find orders of elements in Z_{35} |

The implications of this wicked construct, the grupoid Z

_{n}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 Z

_{n}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

**relatively prime to n when n is the product of two distinct primes p and q where p >2 and q >2.***a*
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

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

In other words, the group composed of all integers co-prime with n does not have any elements

*relatively prime to n if***a****a**has order**k, then**_{ }by Lagrange's Theorem the order of*divides the order of the group , namely k divides φ(n). Since it was assumed that φ(n) is the smallest integer such that***a***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

**relatively prime to n, whose order equals φ(n).Therefore, φ(n) is not the smallest integer such that***a**a*^{φ(n)}= 1 for any**relatively prime to n when n is the product of two distinct primes p and q where p >2 and q >2.***a*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:

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.

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 2

^{2000}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, a

^{2}, a

^{4},..., a

^{2k}mod n can be found, and from there the least positive residues mod n of a

^{2j}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

*((log*

**O**_{2}n)

^{2}log

_{2}i)

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