300 PROPERTIES OF THE INTEGERS [CHAP. 11DIVISIBILITY, GREATEST COMMON DIVISORS, PRIMES
11.84. Find all possible divisors of: (a) 24; (b) 19683= 39 ; (c) 432= 24 · 33.
11.85. List all prime numbers between 100 and 150.
11.86. Express as a product of prime numbers: (a) 2940; (b) 1485; (c) 8712; (d) 319 410.
11.87. For each pair of integersaandb, findd=gcd(a, b)and findmandnsuch thatd=ma+nb:(a) a=356,b=48; (b)a=1287,b=165; (c)a=2310,b=168; (d)a= 195 ,b=968;
(e)a= 249 ,b=37.11.88. Find: (a) lcm(5, 7); (b) lcm(3, 33); (c) 1cm (12, 28).
11.89. Supposea=5880 andb=8316. (a) Expressaandbas products of primes.
(b) Find gcd(a, b)and lcm(a, b). (c) Verify that lcm(a, b)=|ab|/gcd(a, b).
11.90. Prove: (a) Ifa|b, then (i)a|−b, (ii)−a|b, (iii)−a|−b;(b) Ifac|bc, thenb|c.
11.91. Prove: (a) Ifn>1 is composite, thennhas a positive divisordsuch thatd≤
√
n. (b) Ifn>1 is not divisible
by a primep≤
√
n, thennis a prime.
11.92. Prove: (a) Ifam+bn=1, then gcd(a, b)=1; (b) Ifa=bq+r, then gcd(a, b)=gcd(b, r).
11.93. Prove: (a) gcd(a, a+k)dividesk; (b) gcd(a, a+ 2 )equals 1 or 2.
11.94. Prove: (a) Ifa>2 andk>1, thenak−1 is composite. (b) Ifn>0 and 2n−1 is prime, thennis prime.
11.95. Letnbe a positive integer. Prove:
(a) 3 dividesnif and only if 3 divides the sum of the digits ofn.
(b) 9 dividesnif and only if 9 divides the sum of the digits ofn.
(c) 8 dividesnif and only if 8 divides the integer formed by the last three digits ofn.
11.96. Extend the definition of gcd and lcm to any finite set of integers, that is, for integersa 1 ,a 2 ,...,ak, define:
(a) gcd(a 1 ,a 2 ,...,ak); (b) lcm(a 1 ,a 2 ,...,ak).
11.97. Prove: Ifa 1 |n, a 2 |n,...,ak|n, thenm|nwherem=lcm(a 1 ,a 2 ,..., ak).
11.98. Prove: There are arbitrarily large gaps between prime numbers, that is, for any positive integerk, there existk
consecutive composite (nonprime) integers.CONGRUENCES
11.99. Which of the following are true?
(a) 224≡ 762 (mod 8); (b) 582≡ 263 (mod 11); (c) 156≡ 369 (mod 7); (d)− 238 ≡ 483 (mod 13).11.100.Find the smallest nonnegative integer which is congruent modulom=9 to each of the following numbers:
(a) 457; (b) 1578; (c)−366; (d)−3288. (The integer should be in the set{ 0 , 1 , 2 ,..., 7 , 8 }).
11.101.Find the smallest integer in absolute value which is congruent modulom=9 to each of the following numbers:
(a) 511; (b) 1329; (c)−625; (d)−2717. (The integer should be in the set {−4,−3,−2,−1, 0, 1, 2, 3, 4}).
11.102.Find all numbers between 1 and 100 which are congruent to 4 modulom=11.
11.103.Find all numbers between−50 and 50 which are congruent to 12 modulom=9.
RESIDUE SYSTEMS, EULER PHI FUNCTIONφ
11.104. 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=11; (b)m=14.
11.105. Exhibit a reduced residue system modulomand findφ(m)where: (a)m=4; (b)m=11; (c)m=14;
(d)m=15.
11.106.Exhibit a complete residue system modulom=8 consisting entirely of: (a) multiples of 5; (b) powers of 3.
11.107.Show that{ 12 , 22 , 32 ,...,m^2 }is not a complete residue system modulomform>2.
11.108. Find: (a)φ(10); (b)φ(12); (c)φ(15); (d)φ(3^7 ); (e)φ(5^6 ); (f)φ( 24 · 76 · 133 ).