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

292 PROPERTIES OF THE INTEGERS [CHAP. 11

RESIDUE SYSTEMS, EULER PHI FUNCTIONφ

11.38. For each modulom, exhibit two complete residue systems, one consisting of the smallest nonnegative
integers, and the other consisting of the integers with the smallest absolute values: (a)m=9; (b)m=12.
In the first case choose{ 0 , 1 , 2 ,...,m− 1 }, and in the second case choose

{−(m− 1 )/ 2 ,...,− 1 , 0 , 1 ,...,(m− 1 )/ 2 } or {−(m− 2 )/ 2 ,...,− 1 , 0 , 1 ,...,m/ 2 }

according asmis even or odd:

(a) {0, 1, 2, 3, 4, 5, 6, 7, 8} and {−4,−3,−2,−1, 0, 1, 2, 3, 4}

(b) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} and {−5,−4,−3,−2,−1, 0, 1, 2, 3, 4, 5, 6}.

11.39. Find a reduced residue system modulomandφ(m)where: (a)m=9; (b)m=16; (c)m=7.

Choose those positive numbers less thanmand relatively prime tom. The number of such numbers isφ (m).

(a) {1, 2, 4, 5, 7, 8}; henceφ(9)=6.

(b) {1, 3, 5, 7, 9, 11, 13, 15}; henceφ(16)=8.

(c) {1, 2, 3, 4, 5, 6}; henceφ(7)=6. (This is expected sinceφ(p)=p−1 for any primep.)

11.40. RecallSm= 0 , 1 , 2 ,...,m−1 is a complete residue system modulom. Prove:

(a) Anymconsecutive integers is a complete residue system modulom.

(b) If gcd(a, m)=1, thenaSm={ 0 ,a, 2 a, 3 a,...,(m− 1 )a}is a complete residue system modulom.

(a) Consider any other sequence ofmintegers, say{a, a+ 1 ,a+ 2 ,...,a+(m− 1 )}. The absolute value of

the differencesof any two of the integers is less thanm. Thusmdoes not divides, and so the numbers are

incongruent modulom.

(b) Supposeax≡ay(modm) wherex, y∈Sm. Since gcd(a, m)=1, the modified cancellation law Theorem

11.24 tells usx≡y(modm). Sincex, y∈Sm, we must havex=y. That is,aSmis a complete residue system

modulom.

11.41. Exhibit a complete residue system modulom=8 consisting entirely of multiples of 3.

By Problem 11.40(b), 3S 8 ={ 0 , 3 , 6 , 9 , 12 , 15 , 18 , 21 }is a complete residue system modulom=8.

11.42. Show that ifpis a prime, thenφ(pn)=pn−pn−^1 =pn−^1 (p− 1 ).

Clearly, gcd(a, pn)=1 if and only ifpdividesa. Thus the only numbers between 1 andpnwhich are not

relatively prime topnare the multiples ofp, that is,p,2p, 3 p,...,pn−^1 (p). There arepn−^1 such multiples ofp.

All the other numbers between 1 andpnare relatively prime topn. Thus, as claimed:

φ(pn)=pn−pn−^1 =pn−^1 (p− 1 ).

11.43. Find: (a)φ(81),φ( 76 ); (b)φ(72),φ(3000).

(a) By Problem 11.42,

φ( 81 )=φ( 34 )= 33 ( 3 − 1 )= 27 ( 2 )=54 and φ( 76 )= 75 ( 7 − 1 )= 6 ( 75 )

(b) Use Theorem 11.24 thatφis multiplicative:

φ( 72 )=φ( 32 · 23 )=φ( 32 )φ( 23 )= 3 ( 3 − 1 )· 22 ( 2 − 1 )= 24

φ( 3000 )=φ( 3 · 22 · 53 )=φ( 3 )φ( 22 )φ( 53 )= 2 · 2 · 52 ( 5 − 1 )= 400