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}.

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 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s