Chapter 8 Number Theory294
Problems for Section 8.7
Practice Problems
Problem 8.29.
A majority of the following statements are equivalent to each other. List all state-
ments in this majority. Assume thatn > 0andaandbare integers. Briefly explain
your reasoning.
1.ab .modn/
2.aDb
- rem.a; n/Drem.b; n/
4.nj.a b/
- 9 k 2 Z:aDbCnk
6..a b/is a multiple ofn
7.njaORnjb
Homework Problems
Problem 8.30.
Prove that congruence is preserved by arithmetic expressions. Namely, prove that
ab .modn/; (8.33)
then
eval.e;a/eval.e;b/ .modn/; (8.34)
for alle 2 Aexp (see Section 6.4).
Problem 8.31.
The sum of the digits of the base 10 representation of an integer is congruent mod-
ulo 9 to that integer. For example
763 7 C 6 C3 .mod9/:
This is not always true for the hexadecimal (base 16) representation, however. For
example,
.763/ 16 D 7 162 C 6 16 C 3 1 6 7 7 C 6 C3 .mod9/: