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* = 5*k* + 3, where *k* is an integer. Substituting this into the second congruence gives . Since , , so by cancellation we have . Writing *k* = 7*j*+2, we get* x* = 5*k* + 3 = 35*j* + 13.

Substituting this into the third congruence, we get so

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

Problem 2: Find all integers x such that .

*Solution* : Since 125 = 5^{3}, 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* = 5*k*+2.

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

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

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

[ *Question : what about the case ? *]

Problem 3: Find the remainder when 3^{2011}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: Ifpis prime andais an integer not divisible byp, 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 . ♦