8.9. What has SAT got to do with it? 219
(b)Describe in general how to find the gcd.m;n/and lcm.m;n/from the prime
factorizations ofmandn. Conclude that equation (8.11) holds for all positive
integersm;n.
Problems for Section 8.5
Homework Problems
Problem 8.8.
Prove that congruence is preserved by arithmetic expressions. Namely, prove that
ab .modn/; (8.12)then
eval.e;a/eval.e;b/ .modn/; (8.13)
for alle 2 Aexp (see Section 7.4).
Class Problems
Problem 8.9.
The following properties of equivalence modnfollow directly from its definition
and simple properties of divisibility. See if you can prove them without looking up
the proofs in the text.
(a)Ifab .modn/, thenacbc .modn/.(b)Ifab .modn/andbc .modn/, thenac .modn/.(c)Ifab .modn/andcd .modn/, thenacbd .modn/.(d)rem.a;n/a .modn/.Problem 8.10. (a)Why is a number written in decimal evenly divisible by 9 if and
only if the sum of its digits is a multiple of 9?Hint: 10 1 .mod9/.
(b)Take a big number, such as 37273761261. Sum the digits, where every other
one is negated:
3 C. 7/C 2 C. 7/C 3 C. 7/C 6 C. 1/C 2 C. 6/C 1 D 11Explain why the original number is a multiple of 11 if and only if this sum is a
multiple of 11.