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

1. (6 points) Find out whether it is possible to express 1 as a linear combination 1 = 11 · m + 27 · n for some integers m and n, and if it is, find them. Sol. to 1: gcd(27, 11) = gcd(11, 5) = gcd(5, 1) = gcd(1, 0) = 1. So gcd(27, 11) = 1 and it is possible. Now let’s do it.

27 = 2 · 11 + 5 ,

so

5 = 27 − 2 · 11 .
11 = 2 · 5 + 1 ,

so

1 = 11 − 2 · 5 = 11 − 2 · (27 − 2 · 11)
= 11 − 2 · 27 + 4 · 11 = 5 · 11 − 2 · 27 .

So

1 = 5 cot 11 + (−2) · 27 .

Ans.: m = 5 n = −2 . Comment: Most people got it right. One student wrote n = 2. Make sure that the sign is correct. 2.(4 points) Find 11^{16} (mod 13) Sol. to 2

11^{2} mod 13 = 121 mod 13 = 4

(since 121 = 13 · 9 + 4) .

11^{4} = 4^{2} mod 13 = 16 mod 13 = 3
11^{8} = 3^{2} mod 13 = 9
11^{16} = 9^{2} mod 13 = 81 mod 13 = 3 ,

(since 81 = 13 · 6 + 3). Ans.: 11^{16} ≡ 3 (mod 13). Comment: A faster way (done by Richard Wong) is to first use the fact that

11 ≡ −2 (mod 13) ,

and that (−1)^{16} = 1. So we have 11^{16} (mod 13) ≡ (−2)^{16} (mod 13) ≡ 2^{16} (mod 13) .

Now things are a bit simpler (coputationally)

2^{2} mod 13 = 4

2^{4} mod 13 = 4^{2} mod13 = 3

2^{8} mod 13 = 3^{2} mod13 = 9 = −4 mod13

(−4)^{2} mod 13 = 16 mod 13 = 3 .

The trick is that whenver you encounter an integer i than half the modulo m, replace it by by its ‘negative’ −(m − i).