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