The so-called Phi function, developed by the great Swiss mathematician, Leonard Euler, is involved in many theorems of number theory and other branches of mathematics.

THE PHI FUNCTION

The number of positive integers less than n that are relatively prime to n is denoted ϕ(n). The first few values of this important function, called the Euler ϕ function, are given by ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4, ϕ(6) = 2 (since only 1 and 5 are relatively prime to 6), ϕ(7) = 6, ϕ(8) = 4, ϕ(9) = 6, and ϕ(10) = 4.

Observe that if p is a prime, ϕ(p) = p − 1. To calculate ϕ(p^k), notice that the numbers less than or equal to p^k that are not relatively prime to it are the p^k−1 multiples of p, namely, p, 2p, 3p, …, p^k−1p. Since there are p^k positive integers less than or equal to p^k, subtraction yields . When p = 2, this yields ϕ(2^k) = 2^k(½) = 2^k−1, which is in perfect agreement with our earlier observation that ϕ(8) = 4.

Observe, also, that ϕ(n) is even when n > 1. To see this, observe that given a such that 1 ≤ a ≤ n, then gcd(a,n) = 1 if and only if gcd(n − a, n) = 1, since any divisor of a and n must also divide n − a, while any divisor of n − a and n must also divide their sum, a. (For example, both 7 and 13 are relatively prime to 20, while neither of 5 and 15 is.)

We claim that ϕ is multiplicative, that is, if a and b satisfy gcd(a,b) = 1, then ϕ(ab) = ϕ(a)ϕ(b). The proof is difficult and we will skip it.

If , we have, since ϕ is multiplicative, ϕ(n)=ϕ() , which yields the elegant formula

(7.1)

Let . Then f is multiplicative, since ϕ is. To evaluate f(n), assume first that n = p^k, where p is prime. Then we have , from which it follows that f(n) = n. This yields the identity

(7.2)

Here is another proof of (7.2), which we will present for the special case n = 12 but whose generality will be apparent. Consider the 12 fractions 1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12, and 12/12. When we reduce these 12 fractions to lowest terms, the denominators will be the divisors of 12, namely, 1, 2, 3, 4, 6, and 12. The number of fractions for a divisor, d, of 12 will be precisely ϕ(d). Thus, for d = 4 (for which ϕ(4) = 2), we get the 2 reduced fractions 1/4 and 3/4 from 3/12 and 9/12, respectively, while for d = 6 (for which ϕ(6) = 2), we get the 2 reduced fractions 1/6 and 5/6 from 2/12 and 10/12, respectively.

Applying Möbius inversion to (7.2) yields the identity

or more to the point,

(7.3)

How do we reconcile formulas (7.1) and (7.3)? It would require equating the right sides of both formulas, canceling the n and then showing that the resulting equation is true, that is, we must show that

Now, since μ(d) = 0 unless d is square-free, the only nonvanishing terms on the right will result when d = p_i, p_ip_j, p_ip_jp_k, etc., that is, when d is the product of some (or all) of the primes p₁, p₂, …, p_r, each of which is raised to the power 1. Now, μ(d) will be either 1 or −1, depending on the parity of the number of primes in d. Thus, the sum on the right will agree with the sum on the left since they will yield precisely the same terms. For example, the term , occurring on the left, will certainly occur on the right since μ(p₁p₂p₃) = −1, with an analogous statement concerning a term such as .

Let’s add up all the numbers less than n and relatively prime to it. If a is such a number, so is n − a, as we observed earlier in the chapter. There are ϕ(n)/2 such pairs, each with sum n. It follows that the sum of all the numbers less than n and relatively prime to it is nϕ(n)/2. Stated formally, we have

EULER’S GENERALIZATION OF FERMAT’S LITTLE THEOREM

Recall the theorem of Chapter 5 that says that ax = b (mod n) is solvable if and only if gcd(a,n) | b, and then consider the modular equation ax = 1 (mod n). It follows that this is solvable if and only if gcd(a,n) = 1. We then see that a least residue, a (mod n), has a multiplicative inverse if and only if gcd(a,n) = 1. Then there are exactly ϕ(n) such residues. If we multiply each of the members of this set of invertible numbers by any one of them, we must get a rearrangement of the set. (For example, the four invertible residues of n = 10 are 1, 3, 7, and 9. If we multiply each of them by, say, 3, we get 3, 9, 21, and 27, which, when reduced mod 10, yield 3, 9, 1, and 7, which is a rearrangement of the original set, 1, 3, 7, 9.)

Using an argument analogous to the one Fermat used to get his Little Theorem, Euler reasoned as follows. Let the invertible residues of n be a₁, a₂, …, a_r, where r = ϕ(n). Then let gcd(a,n) = 1 in which case (aa₁)(aa₂)…(aa_r) = a₁a₂…a_r (mod n). This becomes a^r = 1 (mod n) after we cancel the product a₁a₂…a_r, a legal operation since gcd(a_i,n) = 1 for each i = 1, 2, …, r. Thus, Euler proved the following generalization of Fermat’s Little Theorem.

Observe that when n is a prime p, we have ϕ(n) = ϕ(p) = p − 1, in which case we get Fermat’s Little Theorem, a^p−1 = 1 (mod p) as a special case of the above more general theorem.

PHI OF A PRODUCT OF m AND n WHEN gcd(m,n) > 1

Here is a theorem concerning ϕ(mn) when m and n are not necessarily relatively prime. We then cannot conclude that ϕ(mn) = ϕ(m)ϕ(n).

Of course, when gcd(m,n) = 1, the above theorem reduces to ϕ(mn) = ϕ(m)ϕ(n), as one would expect, since ϕ is multiplicative.

THE ORDER OF a (mod n)

Given a, such that 1 ≤ a < n and gcd(a,n) = 1, we define the order of a (mod n) denoted |a| (not to be confused with “absolute value”) as the smallest positive exponent, k, such that a^k = 1 (mod n). Such a k must exist in light of Euler’s theorem and must satisfy k ≤ ϕ(n). If gcd(a,n) = d > 1, the order of a does not make sense, since it is then impossible for a^k = 1 (mod n). To see this, note that a^k = 1 (mod n) is equivalent to the equation a^k = 1 + jn for some j. But this is absurd since d | a^k, while d does not divide 1 + jn.

Suppose |a| = k (mod n), then we claim that a^j = 1 (mod n) if and only if k | j. The “if” part is easy. If k | j, then j = km. Then a^j = a^km = (a^k)^m = 1^m = 1 (mod n). For the “only if” part, assume that a^j = 1 (mod n) and using the Euclidean division equation, j = qk + r, where 0 ≤ r < k. Then a^j = a^qk+r = (a^k)^qa^r = a^r (mod n). Since a^j = 1 (mod n), we have a^r = 1 (mod n), implying that r = 0, since r < k and k is the order of a. Then j = qk, implying that k | j. We have proved the following:

PRIMITIVE ROOTS

If |a| mod n is ϕ(n), then a is called a primitive root of n. Thus, 3 is a primitive root of 7 since 3⁶ = 1 (mod 7) and 6 is the smallest exponent that does this. On the other hand, 2 is not a primitive root of 7 since 2³ = 1 (mod 7) and ϕ(7) = 6. Similarly, 3 is not a primitive root of 8 since 3² = 1 (mod 8) and ϕ(8) = 4.

While some numbers such as 15 have no primitive roots (see the exercises at the end of the chapter), it can be shown using group theory (a branch of mathematics beyond the scope of this text) that every odd prime, p, has a primitive root, a, where 2 ≤ a ≤ p − 2. The first p − 1 powers of a (mod p) generate all the numbers 1, 2, …, p − 1, in some order. That is, the set of numbers a, a², a³, …, a^p−1 is a complete set of nonzero residues of p. Necessarily, |a| = p − 1. Of course a ≠ 1 or p − 1, since 1² = (p − 1)² = 1(mod p).

THE INDEX OF m (mod p) RELATIVE TO a

As a consequence of the preceding paragraph about the primitive root a for the odd prime p, given a number m such that 1 ≤ m < p, there exists an exponent r such that a^r = m (mod p). We call r the index of m (mod p) relative to a. In symbols, we write ind_am = r (mod p).

Here is a chart of the indices, mod 13, using the primitive root a = 6.

Let us calculate ind₆(2 × 3). Now, ind₆2 = 5 and ind₆3 = 8, meaning that 6⁵ = 2 (mod 13) and 6⁸ = 3 (mod 13). It follows, upon multiplying these two equations, that 6¹³ = 6 (mod 13). Since, by Fermat’s Little Theorem, 6¹² = 1 (mod 13), this becomes 6¹ = 6 (mod 13), showing that ind₆(2 × 3) = [ind₆2 + ind₆3] (mod 12), since 6¹² = 1 (mod 13).

Here is another example. To calculate ind₆(3 × 4), observe that ind₆3 = 8 and ind₆4 = 10, meaning that 6⁸ = 3 (mod 13) and 6¹⁰ = 4 (mod 13). It follows, upon multiplying these two equations, that 6¹⁸ = 12 (mod 13). Since, by Fermat’s Little Theorem, 6¹² = 1 (mod 13), this becomes 6⁶ = 12 (mod 13), from which it follows that ind₆12 = 6. Then ind₆(3 × 4) = [ind₆3 + ind₆4] (mod 12) = 18 (mod 12) = 6.

Observe that ind₆1 = 0 (mod 12) and observe that ind₆8 = ind₆2³ = 3 × ind₆2 = 3 × 5 = 3 (mod 12), in agreement with the value of ind₆8 in the above chart. All of these observations suggest the following parallels between indices and logarithms:

1. ind_amn = [ind_am + ind_an] (mod p − 1).
2. ind_amⁿ = [n × ind_am] (mod p − 1).
3. ind_a1 = 0 (mod p − 1).
4. ind_aa = 1 (mod p − 1).

Let a be a primitive root of the odd prime p. Then as we observed in the preceding section, the numbers a, a², a³, …, a^p−1 constitute a complete set of nonzero residues of p. Furthermore, the order of a^r for any r between 1 and p − 1 divides p − 1, that is, (|a^r|) | p − 1. We shall determine the order of a^r as a function of r, that is, given r, we will determine |a^r|. Toward this end, let gcd(r, p − 1) = d. Then r = ud and p − 1 = vd, where gcd(u,v) = 1. (See section “Greatest Common Divisor” of Chapter 4 concerning the gcd.) We claim that . We have (a^r)^v = (a^ud)^v = (a^vd)^u = (a^p−1)^u = 1 (mod p). Furthermore, we claim that v is the smallest number that does this. To see this, let |a^r| = k. Then a^rk = 1 (mod p). It follows that p − 1 | rk. Rewrite this as vd | udk, which is equivalent to v | uk. Now, since gcd(u,v) = 1, this requires that v | k. Clearly, the smallest value of k that satisfies this is v. We have proven the following theorem.

Now, suppose d | p − 1, where p is an odd prime with primitive root a. Then p − 1 = dk, in which case |a^k| = d. This can be seen as follows. Firstly, (a^k)^d = a^p−1 = 1. Secondly, for any r < d, we have kr < kd, in which case a^kr ≠ 1, since a is a primitive root. So |a^k| = d. Then given any divisor d of the odd prime p with primitive root a, there is at least one number of order d, namely, a^k, where . This raises the question: how many numbers have order d?

Consider the d numbers a^k, a^2k, a^3k, …, a^dk, no two of which are congruent mod p. (To see this, note that if a^ik = a^jk (mod p) where 1 ≤ i < j ≤ d, then we would have 1 = a^(i−j)k (mod p) where (i − j)k < dk = p − 1, contradicting the fact that a is a primitive root.)

Clearly, any number of this form, that is, a^tk where 1 ≤ t ≤ d, satisfies (a^tk)^d = (a^t)^dk = (a^t)^p−1 = 1 (mod p). This does not imply that |a^tk| = d. An exponent r < d might do the job. In other words, perhaps (a^tk)^r = 1 (mod p). In fact, this will occur precisely when gcd(t,d) > 1, as can be seen as follows. Let gcd(t,d) = s > 1. Then t = us and d = vs, where gcd(u,v) = 1. Then letting r = v < d, we have (a^tk)^r = (a^usk)^v = (a^u)^vsk = (a^u)^dk = (a^u)^p−1 = 1 (mod p). Now, according to a corollary to Lagrange’s theorem (see Chapter 5), the equation x^d − 1 = 0 (mod p) has exactly d distinct roots mod p. Letting x = a^k, this implies that the ϕ(d) numbers less than, and relatively prime to d yield precisely those exponents t for which (a^k)^t = 1 (mod p). Then letting g(d) be the number of incongruent integers of order d, we have g(d) ≤ ϕ(d). It follows that . On the other hand, both sums must equal p − 1, the first because each of the p − 1 positive integer less than p must have an order that divides p − 1 and the second by Equation (7.2), which proves the following theorem.

Note that this theorem generalizes the previous corollary that stated that the number of primitive roots of the odd prime p is ϕ(p − 1).

Note that this corollary was presented as a theorem in Chapter 5.

TO BE OR NOT TO BE A QUADRATIC RESIDUE

Recall that a is a quadratic residue mod p, if x² = a (mod p) has a solution. Otherwise, x is called a quadratic nonresidue. The following interesting corollary follows by the previous theorem upon letting k = 2, in which case d = gcd(2, p − 1) = 2.

To summarize the above two corollaries, we have the following theorem.

THE LEGENDRE SYMBOL

The preceding theorem motivated the French mathematician Legendre (1752–1833) to define the symbol (a/p) where gcd(a,p) = 1 and p is an odd prime, as follows:

(a/p) is called a Legendre symbol. Its use simplifies matters. The above remark, for example, can be stated as

(7.4)

Here are a few properties of the Legendre symbols. The proofs are left as exercises. We assume that gcd(a,p) = gcd(b,p) = 1:

1. If a = b (mod p), then (a/p) = (b/p).
2. (1/p) = 1.
3. .
4. (a²/p) = 1.
5. (ab/p) = (a/p)(b/p), that is, (a/p) is multiplicative.
6. (ab²/p) = (a/p).

Property 3 implies the following remark.

This remark restates the corollary in the previous section: “Let p be an odd prime. Then x² = −1 (mod p) has a solution if and only if p = 1 (mod 4). In other words, −1 is a quadratic residue of p if and only if p = 1 (mod 4).”

We shall use the above remark to show that there are infinitely many primes of the form 4k + 1.

QUADRATIC RECIPROCITY

The following elegant theorem was discovered by Legendre who failed to prove it. Gauss supplied a proof at the age of 19 and went on to find six more proofs! We shall not prove it here.

LAW OF QUADRATIC RECIPROCITY

An immediate and very useful consequence is given by the following corollary.

WHEN DOES x² = a (mod n) HAVE A SOLUTION?

When does x² = a (mod n), where n is a composite number, have a solution? We begin our analysis when n = p^m where p is an odd prime. Here is an important theorem toward this end.

Since the previous theorem deals with powers of an odd prime, it is natural to ask when is an odd number, a, a quadratic residue mod 2ⁿ? Since a = 1 (mod 2), we see that every odd number is a quadratic residue mod 2. Since all odd number are congruent to either 1 or 3 mod 4, and since 1 is a quadratic residue of 4 while 3 is not, it follows that the odd number, a, is a quadratic residue mod 4 if and only if a = 1 (mod 4). Similarly, the only odd quadratic residue of 8 is 1, since 1² = 3² = 5² = 7² = 1 (mod 8).

To complete the analysis of the odd quadratic residues of 2ⁿ, we have the following:

The next theorem combines the last few results. The proof is left as an exercise.

EXERCISES

An asterisk (*) indicates that the exercise can be developed into a research project.

1. Find ϕ(1000), ϕ(5040), ϕ(10ⁿ), and ϕ(10!).
2. Verify the following statements for n ≤ 7:

   Show that ϕ(3ⁿ) = 2 × 3ⁿ⁻¹. Prove this for all n.

   If n is even, show that ϕ(2n) = 2 × ϕ(n).

   Let n = 2^m, where m is odd. Show that ϕ(n) is a square.

   If 3 | n, show that ϕ(3n) = 3 × ϕ(n).

   If 3 does not divide n, show that ϕ(3n) = 2 × ϕ(n).

   If m | n, show that ϕ(m) | ϕ(n).

3. Let p be a prime. Show that p − 1 | ϕ(p^k) for all k ≤ 7 and p ≤ 101.
4. Let p be a prime such that p | n. Show that p − 1 | ϕ(n) for all n ≤ 100.
5. Find 100 values of k such that 10 | ϕ(k).
6. Find 100 values of k such that ϕ(k) = k/3.
7. Show that ϕ(n²) = nϕ(n) for all n ≤ 100.
8. ^*Show that ϕ(n^k) = n^k−1ϕ(n) for all n ≤ 100.
9. Find the last digit of 3³⁴⁵. In other words, find the remainder when 3³⁴⁵ is divided by 10.
10. ^*For all values of n up to 50, show that the sum of the ϕ(n) numbers less than and relatively prime to n is 0 (mod n). Skip n = 1 and n = 2.
11. ^*Show that , where p₁, p₂, …, p_r are the prime divisors of n.
12. ^*Show that if n is even, then . First, confirm this using a program for all n ≤ 7.
13. Show that for all n ≤ 7.
14. If f is an arithmetic function, show that .
15. Find the order of 2 mod p and the order of 3 mod p for all primes between 5 and 101.
16. Find primitive roots for 11, 13, and 17.
17. ^*Show that 15 has no primitive roots by calculating the orders of 2, 4, 7, 8, 11, 13, and 14. Why does it suffice to calculate only these orders?
18. Show that 4 and 9 have primitive roots 3 and 2, respectively.
19. Given that 2 is a primitive root for 19, find all the primitive roots of 19.
20. How many primitive roots does 31 have? Do this in two ways.
21. ^*Let r be a primitive root for the odd prime p. Show that a is a quadratic residue mod p if and only if ind_ra is even. Hint: if ind_ra = 2 m (mod p), then a = r^2m (mod p).
22. ^*Show, using the previous exercise, that exactly half of the p − 1 nonzero least residues of the odd prime p are quadratic residues.
23. Show that 2 is a primitive root for 19.
24. Given the prime modulus 17, find the number of least residues having each of the orders 1, 2, 4, 8, and 16. Then verify your answers by producing the residues having each of these orders.
25. If a = b (mod p), show that (a/p) = (b/p).
26. Show that (1/p) = 1.
27. Show that .
28. Show that (ab/p) = (a/p)(b/p), that is, show that (a/p) is multiplicative.
29. ^*Solve 5x² + 6x + 1 = 0 (mod 23).
30. Show that 3 is a quadratic residue of 169.
31. Show that 5 is a quadratic residue of 1331.
32. Write a program to find ϕ(n). Then tabulate ϕ(n) for all n ≤ 100. See the program at the end of the chapter.
33. Given the positive integer m, write a program to find all n ≤ 1000 such that ϕ(n) = m.
34. Use the program of the previous exercise to show that there is no n ≤ 1000 for which ϕ(n) = m when m = 14, 26, 34, 38, and 50. (In fact, there is no n at all for these values of m. There are infinitely many m’s such that there is no n for which ϕ(n) = m.) On the other hand, show that there are several values of n for which ϕ(n) = 12.
35. The number 18 has an interesting property. ϕ(18) = 6, since the numbers 1, 5, 7, 11, 13, and 17 are relatively prime to 18. All of these numbers (except 1) are prime. Find all numbers with this property. Hint: it is known that no number larger than 30 has this property.
36. Given the prime p and the positive integer a such that gcd(a,p) = 1, write a program to find |a| (mod p).

The Euler Phi Function from Definition

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>PHI function</title>
<script>
 var placeref;
function find(){
 placeref = document.getElementById("place");
 placeref.innerHTML = "";
 n = parseInt(document.f.num.value);

 ans = phi(n);
 placeref.innerHTML = "The Euler phi function for
"+String(n)+" is "+String(ans);
 return false;
}
function phi(n) {
  var ans = 0;
  for (var i=1;i<n;i++){
    if (1 == gcd(i,n)){
      ans++;
    }
  }
  return ans;
}
 
function gcd(a,b){
  var holder;
  var r;
  if (b < a) {
   //switch
   
   holder = a;
   a = b;
   b = holder;
  }
  
  r = b % a;
  if (r==0){
     
    return a;
  }
 
  else {
    return gcd(r,a);
 
  }
}
 
 
</script>
</head>
<body>

Enter number <br/>
<form name="f" onsubmit="return find();">
 <input type="number" name="num" value=""/>  
 
  <input type="submit" value="Enter"/>
</form>
<p id="place">
  Messages will go here.
</p>
</body>
</html>

The Euler Phi Function from Formula

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>PHI from formula</title>
<script type="text/javascript" src="primeDecomposition.js"> </script>
<script>
 
function phiFF(){
  var table;
  placeref = document.getElementById("place");
  n = parseInt(document.f.num.value);
  table = buildPrimeDecomposition(n);
  t = n;
  for (var i=0;i<table.length;i++){
    t = t * (1-(1/table[i][0]));
  }
t = Math.floor(t);  
//correction for inaccuracies from floating pt
//arithmetic
  messages = "The value of PHI for "+ String(n)+" is "+ String(t);
  placeref.innerHTML = messages;
  return false;
}
</script>
</head>
<body>

Enter number to see its phi value:
<form name="f" onSubmit="return phiFF();">
 <input type="number" name="num" value=""/>
 <input type="submit" value="Enter integer"/>
</form>
<div id="place">
Answer will go here.
</div>
</body>
</html>

Numbers Whose Euler Phi Function Values Are a Specified Number

<!DOCTYPE HTML>
<html>
<meta charset="UTF-8">
<head>
<title>PHI inverse</title>
<script>
 var placeref;
 var limit = 1000;
 
function find(){
 var m;
 placeref = document.getElementById("place");
 m = parseInt(document.f.num.value);
 message = "";
 placeref.innerHTML = message;
 
 for (var n = 1;n<=limit;n++){
  if (m==phi(n)){
    message+="<br/>"+String(n);
 
   }
  }
  if (message.length<1){
    message = "No values <= "+String(limit)+" have
phi equal to "+String(m);
  }
  else {

    message = "Values <= "+String(limit)+" with phi
equal to "+String(m)+"<br/>"+ message;
  }
  placeref.innerHTML = message;
 
 return false;
}
function phi(n) {
  var ans = 0;
  for (var i=1;i<n;i++){
    if (1 == gcd(i,n)){
      ans++;
    }
  }
  return ans;
}
 
function gcd(a,b){
  var holder;
  var r;
  if (b < a) {
  //switch
   
   holder = a;
   a = b;
   b = holder;
  }
  
  r = b % a;
  if (r==0){
     
    return a;
  }
 
  else {
    return gcd(r,a);
 
  }
}
 
</script>
</head>
<body>

Enter number <br/>
<form name="f" onsubmit="return find();">
 <input type="number" name="num" value=""/>  
 
  <input type="submit" value="Enter"/>
</form>
<p id="place">
  Messages will go here.
</p>
</body>
</html>