Solutions to Quiz # 4 for Dr. Z.’s Number Theory Course for Oct. 17, 2013

1. Using the the formula find the unique x between 0 and 44 such that

x ≡ 3 (mod 5) , x ≡ 5 (mod 9) .

Solution to 1.: The formula is: The solution of the system

x ≡ a_{1} (mod m_{1}) , x ≡ a_{2} (mod m_{2}) .

is

x = a_{1}m_{2}[m_{2}^{−1}]_{m_{1}} + a_{2}m_{1}[m_{1}^{−1}]_{m_{2}}

Here m_{1} = 5 and m_{2} = 9. Since gcd(5, 9) = 1 we are guaranteed a solution, but let’s find both [9^{−1}]_{5} and [5^{−1}]_{9}. We can do it at the same time by doing the Extended Euclidean algorithm for 5 and 9.

9 = 1 · 5 + 4 ,

Hence

4 = 9 − 1 · 5 .

Next

5 = 1 · 4 + 1 ,

Hence

1 = 5 − 4 = 5 − (9 − 1 · 5) = 2 · 5 − 1 · 9

So we got

1 = 2 · 5 − 1 · 9 .

Taking it mod 5 we get

1 ≡ (−1) · 9 (mod 5) ,

so [9^{−1}]_{5} = −1 (= 4). It is easier to keep it as −1. Taking it mod 9, we get

1 ≡ 2 · 5 (mod 9) ,

so [5^{−1}]_{9} = 2. Since a_{1} = 3 and a_{2} = 5 we have

x ≡ 3 · 9 · [9^{−1}]_{5} + 5 · 5 · [5^{−1}]_{9} (mod 45)
≡ 3 · 9 · (−1) + 5 · 5 · 2 (mod 45)
≡ −27 + 50 (mod 45) ≡ 23 (mod 45) .

But this is not the final answer. The question asked for an integer NOT a congruence class! The unique integer between 0 and 44 that satisfies the two conditions of the problem is x = 23.

Ans. to 1.: x = 23.

Note about partial credit policy: Quite a few people followed the right method and formula, but made careless computational mistakes that lead to the wrong answer. It is OK to make mistakes, but in this problem (and many other problems in this class), it is very easy to check your answer.

In this case 23 modulo 5 = 3 and 23 modulo 9 = 5, so you know that you got the right answer. Suppose that you made a careless error and got x = 20, then 20 modulo 5 = 0 and you know right away that you made a mistake.

If you would write: “I realize that I made an error, since my answer does not agree with the conditions”, you would get more partial credit.