Mathematics for Computer Science

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

3. rem.a; n/Drem.b; n/

4.nj.ab/

5. 9 k 2 Z:aDbCnk

6..ab/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/: