Elementary Number Theory with Programming

7THE EULER PHI FUNCTION

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.

Computing the Euler phi function from the definition can be done using a gcd function. I started with the function from a previous chapter and removed the display of messages. The document has three functions: find for the interaction with the user, gcd for returning the greatest common divisor, and phi for checking each number from 1 to the specified number n. The find function is invoked by action of the form. The find function invokes the phi function, which invokes the gcd function. The phi function contains a for-loop and checks and computes the gcd value of the loop variable and n. If the value is one, a variable named ans is incremented. When the loop is complete, the ans value is returned. The find function displays the results.

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