O'Reilly logo

Elementary Number Theory with Programming by Jeanine Meyer, Marty Lewinter

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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.

Observe that if p is a prime, ϕ(p) = p − 1. To calculate ϕ(pk), notice that the numbers less than or equal to pk that are not relatively prime to it are the pk−1 multiples of p, namely, p, 2p, 3p

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required