The tutor solves a system of linear congruences.

Back in my post from March 25, 2014, I explain that “mod” means remainder: for instance, 7 mod 3 = 1.

Two numbers that, divided by a number n, give the same remainder, are called congruent mod n. For example, 24 mod 5 = 4, and also 29 mod 5 = 4. Therefore, 24 is congruent to 29 mod 5. This can be written

24 ≡ 29 mod 5

Example: question 10a, page 41, from Underwood Dudley:

Consider the system of linear congruences

x + 2y ≡ 3 (mod 9)
3x + y ≡ 2 (mod 9)

Solution: The first congruence suggests that

x + 2y = 9k + 3 for some integer k

⇒ x = 9k + 3 – 2y

Substituting into the second congruence, we get

3(9k + 3 – 2y) + y ≡ 2 (mod 9)

then

27k + 9 -6y + y ≡ 2 (mod 9)

which means

27k + 9 -5y = 9m + 2 for some integer m.

-5y = 9m + 2 – 27k – 9

Therefore,

-5y = 9(m -3k -1) + 2 ≡ 2 (mod 9)

From

-5y ≡ 2 (mod 9)

we can multiply both sides by -1 to arrive at

5y ≡ -2 (mod 9)

Since -2 + 9 = 7, we can rewrite the congruence as

5y ≡ 7 (mod 9)

Mod 9, there are only the integers 0 to 8. Trying each one, we realize y = 5:

5(5) ≡ 7 (mod 9) since 25 mod 9 = 7

If y=5, we can sub it into the first equation

x + 2(5) ≡ 3 (mod 9)

x + 10 ≡ 3 (mod 9)

Subtracting 10 from both sides gives

x ≡ -7 (mod 9)

meaning

x ≡ 2 (mod 9)

So we have x = 9p + 2 and y = 9q +5, for any integers p,q.

I’ll be discussing more about linear congruences in future posts:)

Source:

Dudley, Underwood. Elementary Number Theory,
second edition.  New York: W H Freeman and Company, 1978.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.