Homework 3

3

Homework

P. 3.1. Let a, b ∈ Z be two nonzero integers. a) Prove that if q, r ∈ Z are integers such that a = b · q + r, then (a, b) = (b, r). b) If the sequences (qk )k≥1 and (rk )k≥−1 of integers are defined by r−1 = a , r0 = b , 0 ≤ rk+1 < |rk | : rk−1 = rk · qk+1 + rk+1 , (∀)k ≥ 0 : rk 6= 0 , show that there is a nonnegative integer n such that rn > 0 = rn+1 . Prove that (a, b) = rn . P. 3.2. Let n = ak ak−1 . . . a2 a1 a0 , with ai ∈ {0, 1, . . . , 9}, be the decimal expansion of the positive integer n. Prove the following divisibility criteria: a) 2|n ⇐⇒ 2|a0 (and similar for 5 or 10 in stead of 2). b) 3|n ⇐⇒ 3|a0 + a1 + a2 + . . . + ak−1 + ak (and similar for 9 in stead of 3). c) 4|n ⇐⇒ 4|a1 a0 (similar for 25 and 100). d) 4|n ⇐⇒ 4|a0 + 2a1 . e) 8|n ⇐⇒ 8|a0 + 2a1 + 4a2 . f) 7|n ⇐⇒ 7|ak ak−1 . . . a2 a1 + 5a0 (similar for 49). g) 11|n ⇐⇒ 11|ak ak−1 . . . a2 a1 − a0 . h) 13|n ⇐⇒ 13|ak ak−1 . . . a2 a1 + 4a0 . i) 17|n ⇐⇒ 17|ak ak−1 . . . a2 a1 − 5a0 . j) 19|n ⇐⇒ 19|ak ak−1 . . . a2 a1 + 2a0 . k) 23|n ⇐⇒ 23|ak ak−1 . . . a2 a1 + 7a0 . l) 29|n ⇐⇒ 29|ak ak−1 . . . a2 a1 + 3a0 . m) 31|n ⇐⇒ 31|ak ak−1 . . . a2 a1 − 3a0 .

1