1. Definition of Euler’s Totient Function:

• Euler’s totient function written f(n) , defined as the number of positive integers less than n and relatively prime to n. By conversion, f(1) =1. Examples:

  1. Determine f (37) and f (35).

  2. Because 37 is prime, all of the positive integers from 1 through 36 are relatively prime to 37. Thus f (37) = 36.

  3. To determine f(35) , we list all of the positive integers less than 35 that are relatively prime to it:

     1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33 and 34.

  4. There are 24 numbers on the list, so f(35) =24.

  5. It should be clear that for a prime number p,

     f (p) = p -1

     Now suppose that we have two prime numbers p and q , with pq. Then for

     n= p *q,

     f (n) = f (pq) = f (p) × f (q) = (p-1) × (q-1)

2. Definition of Premitive root:

• If n is a positive integer, the integers between 1 and n − 1 which are coprime to n (or equivalently, the congruence classes coprime to n) form a group with multiplication modulo nas the operation; it is denoted by $Z_n^×$ and is called the group of units modulo n or the group of primitive classes modulo n. This group is cyclic if and only if n is equal to 2, 4, $p_k$, or 2pk where pk is a power of an odd prime number. A generator of this cyclic group is called a primitive root modulo n, or a primitive element of $Z_n^×$.

• The order of (i.e. the number of elements in) $Z_n^×$ is given by Euler's totient function Euler's theorem says that $a^{φ(n)} ≡ 1$ (mod n) for every a co prime to n; the lowest power of a which is congruent to 1 modulo n is called the multiplicative order of a modulo n. In particular, for a to be a primitive root modulo n, $φ(n)$ has to be the smallest power of a which is congruent to 1 modulo n.

• The number 3 is a primitive root modulo 7 because

  $3^1=3=3^0 \times 3 \equiv 1 \times 3 =3 \equiv 3 (mod 7) \\ 3^2=9=3^1 \times 3 \equiv 3 \times 3 = 9 \equiv 2 (mod 7) \\ 3^3=27=3^2 \times 3 \equiv 2 \times 3 = 6 \equiv 6 (mod 7) \\ 3^4=81=3^3 \times 3 \equiv 6 \times 3 = 18 \equiv 4 (mod 7) \\ 3^5=243=3^4 \times 3 \equiv 4 \times 3 = 12 \equiv 5 (mod 7) \\ 3^6=729=3^5 \times 3 \equiv 5 \times 3 = 15 \equiv 1 (mod 7)$