Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 11] PROPERTIES OF THE INTEGERS 293

11.44. Prove Theorem 11.25: Ifaandbare relatively prime, thenφ(ab)=φ(a)φ(b).

Letaandbbe coprime (relatively prime) positive integers, and letSbe the set of numbers from 1 toabarranged

in an array as in Fig. 11-7. That is, the first row ofSis the list of numbers from 1 toa, the second row is the list of

numbers froma+1to2a, and so on. Sinceaandbare coprime, any integerxis coprime toabif and only if it is

coprime to bothaandb. We find the number of such integersxin the arrayS.

Sincena+k≡k(moda), each column inSbelongs to the same residue class moduloa. Therefore, any integer

xinSis coprime toaif and only ifxbelongs to a column headed by some integerkwhich is coprime toa. On the

other hand, there areφ(a) such columns since the first row is a residue system moduloa.

Fig. 11-7

Now let us consider an arbitrary column in the arraySwhich consists of the numbers:

k, a+k, 2 a+k, 3 a+k,...,(b− 1 )a+k (11.11)

By Problem 11.10, thesebintegers form a residue system modulob, that is, no two of the integers are congruent

modulob. Therefore, (11.11) contains exactlyφ(b)integers which are coprime tob. We have shown that the array

Scontainsφ(a) columns consisting of those integers which are coprime to a, and each such column containsφ(b)

integers which are coprime tob. Thus there areφ(a) φ(b)integers in the array S which are coprime to bothaandb

and hence are coprime toab. Accordingly, as required

φ(ab)=φ(a)φ(b)

ARITHMETIC MODULOm, Zm

11.45. Exhibit the addition and multiplication tables for: (a)Z 4 ;(b)Z 7

(a) See Fig. 11-8. (b) See Fig. 11-9.

Fig. 11-8

Fig. 11-9