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

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