Now we will solve actual problems with the theory we’ve just learnt.

Problem 1 : Find all integers x such that x ÷ 5 has remainder 3, x ÷ 7 has remainder 6 and x ÷ 9 has remainder 2.

Solution : This can be written as:

The first congruence gives x = 5k + 3, where k is an integer. Substituting this into the second congruence gives . Since , , so by cancellation we have . Writing k = 7j+2, we get x = 5k + 3 = 35j + 13.

Substituting this into the third congruence, we get so

Write j = 9i+2 and this gives x = 35j + 13 = 315i + 83. ♦

Problem 2 : Find all integers x such that .

Solution : Since 125 = 5³, we shall solve this congruence modulo successive powers of 5. First, we get . This is easily solved by checking: . We consider the case where , i.e. x = 5k+2.

Solving for the next power: . Expanding, we get:

By cancellation, we get . Thus k = 5j+1 so x = 25j + 7. Substituting this into the congruence , we get:

Thus . Writing j = 5i + 4, we get x = 125i + 107. ♦

[ Question : what about the case ? ]

Problem 3 : Find the remainder when 3²⁰¹¹ is divided by 13.

Solution : Note that . Thus, we get:

Hence the answer is 3.♦

Problem 3 thus inspires us to ask the following question: given a and m to find an n > 0 such that .  The case where m is prime is given below.

Fermat’s Little Theorem : If p is prime and a is an integer not divisible by p, then .

To prove this, we use the fact that every integer is congruent to exactly one of {0, 1, …, p-1} modulo p. Now consider the following modulo p:

expressed as an element in {1, …, p-1} (0 is excluded since they are not divisble by p). We write , where and each . Furthermore no two c_i‘s are identical since

since a is not divisible by prime p. Thus, the c_i‘s run through each element of {1, 2, …, p-1} exactly once. Multiplying all the congruence relations together we obtain:

or . By cancellation (since p is prime), we have . ♦