THE ART AND SCIENCE OF MATHEMATICS
Wednesday, November 30, 2005

Euler's $\phi$-function

• If two positive integers have a greatest common divisor equal to 1, then these two integers are said to be relatively prime.

  Exercise: For each integer n from 2 to 12, find all positive integers less than n that are relatively prime to n.

• The Euler phi-function $\phi(n)$ is defined to be the number of positive integers less than n that are relatively prime to n. By definition, the number 1 is relatively prime to n.

  Exercise: Use the result from the previous exercise to determine the values of the Euler phi-function for n from 1 to 12. Do you see a pattern? (You can generate this sequence using Maple: with(numtheory): [ seq(phi(n),n=1..100)]; )

• Show that $\phi(n)$ is even for $n \geq 3$.

• Let a and b be two relatively prime numbers. Show that $\phi(ab)=\phi(a)\phi(b)$. (Thus, $\phi$ is multiplicative.)

• Let p be a prime number and let k be a positive integer. Show that $\phi(p^k)=p^k(1-\frac{1}{p})$.

• If n is not prime, it has prime factors $p_1,\ldots,p_k$ and can be written $n=\Pi_{i=1}^k p_i^{a_i}$ for some positive integers a_i. Show that
  
  $$\phi(n) = n (1-\frac{1}{p_1}) (1-\frac{1}{p_2}) \ldots (1-\frac{1}{p_k}).$$
  
  

• Two numbers are congruent modulo m (written $a \equiv b\pmod m$) if m divides a-b.

  Exercise: For each integer from 0 to 3 find two other integers congruent to it modulo 4.

  Exercise: Suppose that $a \equiv b\pmod m$ and $c \equiv d\pmod m$. Is it true that $a+c \equiv b+d\pmod m$? Can you prove it? Can you prove that $ac \equiv bd\pmod m$?

• A famous and nontrivial result that is also used in data encryption algorithms is Euler's Theorem: If m is a positive integer and a is a positive integer relatively prime to m then
  

  $$a^{\phi(m)} \equiv 1\pmod m.$$
  
  

  Exercise: Verify Euler's Theorem for m=4 and a=9 and for m=5 and a=3.

• Euler's Theorem is a generalization of Fermat's (little) theorem: If p is a prime number that does not divide a then
  

  $$a^{p-1} \equiv 1\pmod m.$$
  
  

Other resources:

• The MathWorld page on the Euler's phi function.
• Three other pages on Euler's phi function and Euler's theorem.
• Pages on RSA encryption.