## Number Theory Notes (22 Oct 2011) – Part II

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:

$x \equiv 3 \pmod 5, \quad x \equiv 6 \pmod 7, \quad x \equiv 2 \pmod 9.$

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

Substituting this into the third congruence, we get $35j + 13 \equiv 2 \pmod 9$ so

$-j \equiv 35j \equiv -11 \pmod 9 \implies j \equiv 2 \pmod 9.$

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

Problem 2 : Find all integers x such that $x^2 \equiv 74 \pmod {125}$.

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

Solving for the next power: $(5k+2)^2 \equiv 24 \pmod {25}$. Expanding, we get:

$25k^2 + 20k + 4 \equiv 24 \pmod {25} \implies 20k \equiv 20 \pmod {25} \implies 4k \equiv 4 \pmod 5.$

By cancellation, we get $k \equiv 1 \pmod 5$. Thus k = 5j+1 so x = 25j + 7. Substituting this into the congruence $x^2 \equiv 74 \pmod {125}$, we get:

$350j + 49 \equiv 74 \pmod {125} \implies 14j \equiv 1 \pmod 5.$

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

[ Question : what about the case $x \equiv 3 \pmod 5$? ]

Problem 3 : Find the remainder when 32011 is divided by 13.

Solution : Note that $3^3 = 27 \equiv 1 \pmod {13}$. Thus, we get:

$3^{2011} = (3^3)^{670} \times 3 \equiv 1^{670} \times 3 \pmod {13}.$

Problem 3 thus inspires us to ask the following question: given a and m to find an n > 0 such that $a^n \equiv 1 \pmod m$.  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 $a^{p-1} \equiv 1 \pmod p$.

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:

$1 \times a, 2 \times a, \dots, (p-1)\times a \pmod p,$

expressed as an element in {1, …, p-1} (0 is excluded since they are not divisble by p). We write $i \times a \equiv c_i \pmod p$, where $i = 1,2,\dots, p-1$ and each $1 \le c_i \le p-1$. Furthermore no two ci‘s are identical since

$c_i = c_j \implies (i - j)a \equiv 0 \pmod p \implies i - j \equiv 0 \pmod p,$

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

$(a) \times (2a) \times \dots \times ((p-1)a) \equiv 1 \times 2 \times \dots \times (p-1) \mod p$

or $(p-1)! a^{p-1} \equiv (p-1)! \pmod p$. By cancellation (since p is prime), we have $a^{p-1} \equiv 1 \pmod p$. ♦

This entry was posted in Notes and tagged , , . Bookmark the permalink.