2 On the Indicator of an Integer

Chapter 2
On the Indicator of an Integer

2.1 Deﬁnition. Indicator of a Prime Power

Deﬁnition. If $m$ is any given positive integer the number of positive integers not greater than $m$ and prime to it is called the indicator of $m$ . It is usually denoted by $φ (m)$ , and is sometimes called Euler’s $φ$ -function of $m$ . More rarely, it has been given the name of totient of $m$ .

As examples we have

φ (1) = 1, φ (2) = 1, φ (3) = 2, φ (4) = 2 .

If $p$ is a prime number it is obvious that

φ (p) = p - 1;

for each of the integers 1, 2, 3, $\dots$ , $p - 1$ is prime to $p$ .

Instead of taking $m = p$ let us assume that $m = p^{α}$ , where $α$ is a positive integer, and seek the value of $φ (p^{α})$ . Obviously, every number of the set 1, 2, 3, $\dots$ , $p^{α}$ either is divisible by $p$ or is prime to $p^{α}$ . The number of integers in the set divisible by $p$ is $p^{α - 1}$ . Hence $p^{α} - p^{α - 1}$ of them are prime to $p$ . Hence $φ (p^{α}) = p^{α} - p^{α - 1}$ . Therefore

If $p$ is any prime number and $α$ is any positive integer, then

φ (p^{α}) = p^{α} (1 - \frac{1}{p}) .

2.2 The Indicator of a Product

I. If $μ$ and $ν$ are any two relatively prime positive integers, then

φ (μ ν) = φ (μ) φ (ν) .

In order to prove this theorem let us write all the integers up to $μ ν$ in a rectangular array as follows:

\begin{aligned} 1 & 2 & 3 & \dots & h & \dots & μ \\ μ + 1 & μ + 2 & μ + 3 & \dots & μ + h & \dots & 2 μ \\ 2 μ + 1 & 2 μ + 2 & 2 μ + 3 & \dots & 2 μ + h & \dots & 3 μ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ (ν - 1) μ + 1 & (ν - 1) μ + 2 & (ν - 1) μ + 3 & \dots & (ν - 1) μ + h & \dots & ν μ \end{aligned}\}

(A)

If a number $h$ in the ﬁrst line of this array has a factor in common with $μ$ then every number in the same column with $h$ has a factor in common with $μ$ . On the other hand if $h$ is prime to $μ$ , so is every number in the column with $h$ at the top. But the number of integers in the ﬁrst row prime to $μ$ is $φ (μ)$ . Hence the number of columns containing integers prime to $μ$ is $φ (μ)$ and every integer in these columns is prime to $μ$ .

Let us now consider what numbers in one of these columns are prime to $ν$ ; for instance, the column with $h$ at the top. We wish to determine how many integers of the set

\begin{matrix} h, μ + h, 2 μ + h, \dots, (ν - 1) μ + h \end{matrix}

are prime to $ν$ . Write

\begin{matrix} s μ + h = q_{s} ν + r_{s} \end{matrix}

where s ranges over the numbers $s = 0, 1, 2, \dots, ν - 1$ and $0 ≦ r_{s} < ν$ . Clearly $s μ + h$ is or is not prime to $ν$ according as $r_{s}$ is or is not prime to $ν$ . Our problem is then reduced to that of determining how many of the quantities $r_{s}$ are prime to $ν$ .

First let us notice that all the numbers $r_{s}$ are diﬀerent; for, if $r_{s} = r_{t}$ then from

s μ + h = q_{s} ν + r_{s}, t μ + h = q_{t} ν + r_{t},

we have by subtraction that $(s - t) μ$ is divisible by $ν$ . But $μ$ is prime to $ν$ and $s$ and $t$ are each less than $ν$ . Hence $(s - t) μ$ can be a multiple of $ν$ only by being zero; that is, $s$ must equal $t$ . Hence no two of the remainders $r_{s}$ can be equal.

Now the remainders $r_{s}$ are $ν$ in number, are all zero or positive, each is less than $ν$ , and they are all distinct. Hence they are in some order the numbers 0, 1, 2, $\dots$ , $ν - 1$ . The number of integers in this set prime to $ν$ is evidently $φ (ν)$ .

Hence it follows that in any column of the array (A) in which the numbers are prime to $μ$ there are just $φ (ν)$ numbers which are prime to $ν$ . That is, in this column there are just $φ (ν)$ numbers which are prime to $μ ν$ . But there are $φ (μ)$ such columns. Hence the number of integers in the array (A) prime to $μ ν$ is $φ (μ) φ (ν)$ .

But from the deﬁnition of the $φ$ -function it follows that the number of integers in the array (A) prime to $μ ν$ is $φ (μ ν) .$ Hence,

φ (μ ν) = φ (μ) φ (ν),

which is the theorem to be proved.

COROLLARY. In the series of $n$ consecutive terms of an arithmetical progression the common diﬀerence of which is prime to $n$ , the number of terms prime to $n$ is $φ (n)$ .

From theorem I we have readily the following more general result:

II. If $m_{1}, m_{2}, \dots, m_{k}$ are $k$ positive integers which are prime each to each, then

φ (m_{1} m_{2} \dots m_{k}) = φ (m_{1}) φ (m_{2}) \dots φ (m_{k}) .

2.3 The Indicator of any Positive Integer

From the results of §§2.1 and 2.2 we have an immediate proof of the following fundamental theorem:

If $m = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{n}^{α_{n}}$ where $p_{1}, p_{2}, \dots, p_{n}$ are diﬀerent primes and $α_{1}, α_{2}, \dots, α_{n}$ are positive integers, then

φ (m) = m (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{n}}) .

For,

\begin{array}{l} φ (m) & = φ (p_{1}^{α_{1}}) φ (p_{2}^{α_{2}}) \dots φ (p_{n}^{α_{n}}) \\ = p_{1}^{α_{1}} (1 - \frac{1}{p_{1}}) p_{2}^{α_{2}} (1 - \frac{1}{p_{2}}) \dots p_{n}^{α_{n}} (1 - \frac{1}{p_{n}}) \\ = m (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{n}}) . \end{array}

On account of the great importance of this theorem we shall give a second demonstration of it.

It is clear that the number of integers less than $m$ and divisible by $p_{1}$ is

\begin{matrix} \frac{m}{p_{1}} . \end{matrix}

The number of integers less than $m$ and divisible by $p_{2}$ is

\begin{matrix} \frac{m}{p_{2}} . \end{matrix}

The number of integers less than $m$ and divisible by $p_{1} p_{2}$ is

\begin{matrix} \frac{m}{p_{1} p_{2}} . \end{matrix}

Hence the number of integers less than $m$ and divisible by either $p_{1}$ or $p_{2}$ is

\begin{matrix} \frac{m}{p_{1}} + \frac{m}{p_{2}} - \frac{m}{p_{1} p_{2}} . \end{matrix}

Hence the number of integers less than $m$ and prime to $p_{1} p_{2}$ is

\begin{matrix} m - \frac{m}{p_{1}} - \frac{m}{p_{2}} + \frac{m}{p_{1} p_{2}} = m (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) . \end{matrix}

We shall now show that if the number of integers less than $m$ and prime to $p_{1} p_{2} \dots p_{i}$ , where $i$ is less than $n$ , is

\begin{matrix} m (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{i}}), \end{matrix}

then the number of integers less than $m$ and prime to $p_{1} p_{2} \dots p_{i} p_{i + 1}$ is

\begin{matrix} m (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{i + 1}}) . \end{matrix}

From this our theorem will follow at once by induction.

From our hypothesis it follows that the number of integers less than $m$ and divisible by at least one of the primes $p_{1}$ , $p_{2}$ , $\dots$ , $p_{i}$ is

\begin{matrix} m - m (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{i}}), \end{matrix}

\begin{matrix} \sum \frac{m}{p_{1}} - \sum \frac{m}{p_{1} p_{2}} + \sum \frac{m}{p_{1} p_{2} p_{3}} - \dots, & (A) \end{matrix}

where the summation in each case runs over all numbers of the type indicated, the subscripts of the $p$ ’s being equal to or less than $i$ .

Let us consider the integers less than $m$ and having the factor $p_{i + 1}$ but not having any of the factors $p_{1}$ , $p_{2}$ , $\dots$ , $p_{i}$ . Their number is

\begin{matrix} \frac{m}{p_{i + 1}} - \frac{1}{p_{i + 1}} \{\sum \frac{m}{p_{1}} - \sum \frac{m}{p_{1} p_{2}} + \sum \frac{m}{p_{1} p_{2} p_{3}} - \dots\}, & (B) \end{matrix}

where the summation signs have the same signiﬁcance as before. For the number in question is evidently $\frac{m}{p_{i + 1}}$ minus the number of integers not greater than $\frac{m}{p_{i + 1}}$ and divisible by at least one of the primes $p_{1}$ , $p_{2}$ , $\dots$ , $p_{i}$ .

If we add (A) and (B) we have the number of integers less than $m$ and divisible by one at least of the numbers $p_{1}$ , $p_{2}$ , $\dots$ , $p_{i + 1}$ . Hence the number of integers less than $m$ and prime to $p_{1}$ , $p_{2}$ , $\dots$ , $p_{i + 1}$ is

\begin{matrix} m - \sum \frac{m}{p_{1}} + \sum \frac{m}{p_{1} p_{2}} - \sum \frac{m}{p_{1} p_{2} p_{3}} + \dots, \end{matrix}

where now in the summations the subscripts run from 1 to $i + 1$ . This number is clearly equal to

\begin{matrix} m (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{i + 1}}) . \end{matrix}

From this result, as we have seen above, our theorem follows at once by induction.

2.4 Sum of the Indicators of the Divisors of a Number

We shall ﬁrst prove the following lemma:

Lemma. If $d$ is any divisor of $m$ and $m = n d$ , the number of integers not greater than $m$ which have with $m$ the greatest common divisor $d$ is $φ (n)$ .

Every integer not greater than $m$ and having the divisor $d$ is contained in the set $d$ , $2 d$ , $3 d$ , $\dots$ , $n d$ . The number of these integers which have with $m$ the greatest common divisor $d$ is evidently the same as the number of integers of the set 1, 2, $\dots$ , $n$ which are prime to $\frac{m}{d}$ , or $n$ ; for $α d$ and $n$ have or have not the greatest common divisor $d$ according as $α$ is or is not prime to $\frac{m}{d} = n$ . Hence the number in question is $φ (n)$ .

From this lemma follows readily the proof of the following theorem:

If $d_{1}$ , $d_{2}$ , $\dots$ , $d_{r}$ are the diﬀerent divisors of $m$ , then

φ (d_{1}) + φ (d_{2}) + \dots + φ (d_{r}) = m .

Let us deﬁne integers $m_{1}$ , $m_{2}$ , $\dots$ , $m_{r}$ by the relations

m = d_{1} m_{1} = d_{2} m_{2} = \dots = d_{r} m_{r} .

Now consider the set of $m$ positive integers not greater than $m$ , and classify them as follows into $r$ classes. Place in the ﬁrst class those integers of the set which have with $m$ the greatest common divisor $m_{1}$ ; their number is $φ (d_{1})$ , as may be seen from the lemma. Place in the second class those integers of the set which have with $m$ the greatest common divisor $m_{2}$ ; their number is $φ (d_{2})$ . Proceeding in this way throughout, we place ﬁnally in the last class those integers of the set which have with $m$ the greatest common divisor $m_{r}$ ; their number is $φ (d_{r})$ . It is evident that every integer in the set falls into one and into just one of these $r$ classes. Hence the total number $m$ of integers in the set is $φ (d_{1}) + φ (d_{r}) + \dots + φ (d_{r})$ . From this the theorem follows immediately.

EXERCISES

1.

Show that the indicator of any integer greater than

2

is even.

2.

Prove that the number of irreducible fractions not greater than

1

and with denominator equal to

n

φ (n)

3.

Prove that the number of irreducible fractions not greater than

1

and with denominators not greater than

n

φ (1) + φ (2) + φ (3) + \dots + φ (n) .

4.

Show that the sum of the integers less than

n

and prime to

n

\frac{1}{2} n φ (n)

n > 1

5.

Find ten values of

x

such that

φ (x) = 24

6.

Find seventeen values of

x

such that

φ (x) = 72

7.

Find three values of

n

for which there is no

x

satisfying the equation

φ (x) = 2 n

8.

Show that if the equation

φ (x) = n

has one solution it always has a second solution, $n$ being given and $x$ being the unknown.

9.

Prove that all the solutions of the equation

φ (x) = 4 n - 2, n > 1,

are of the form $p^{α}$ and $2 p^{α}$ , where $p$ is a prime of the form $4 s - 1$ .

10.

How many integers prime to

n

are there in the set

(a): $1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \dots, n (n + 1)$ ?
(b): $1 \cdot 2 \cdot 3, 2 \cdot 3 \cdot 4, 3 \cdot 4 \cdot 5, \dots, n (n + 1) (n + 2)$ ?
(c): $\frac{1 \cdot 2}{2}, \frac{2 \cdot 3}{2}, \frac{3 \cdot 4}{2}, \dots, \frac{n (n + 1)}{2}$ ?
(d): $\frac{1 \cdot 2 \cdot 3}{6}, \frac{2 \cdot 3 \cdot 4}{6}, \frac{3 \cdot 4 \cdot 5}{6}, \dots, \frac{n (n + 1) (n + 2)}{6}$ ?

11*.

Find a method for determining all the solutions of the equation

φ (x) = n,

where $n$ is given and $x$ is to be sought.

12*.

A number theory function

φ (n)

is deﬁned for every positive integer

n

; and for every such number

n

it satisﬁes the relation

φ (d_{1}) + φ (d_{2}) + \dots + φ (d_{r}) = n,

where $d_{1}, d_{2}, \dots, d_{r}$ are the divisors of $n$ . From this property alone show that

φ (n) = n (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{k}}),

where $p_{1}, p_{2}, \dots, p_{k}$ are the diﬀerent prime factors of $n$ .

ptail

top

Chapter 2On the Indicator of an Integer

2.1 Deﬁnition. Indicator of a Prime Power

2.2 The Indicator of a Product

2.3 The Indicator of any Positive Integer

2.4 Sum of the Indicators of the Divisors of a Number

Chapter 2
On the Indicator of an Integer