MIDTERM EXAM SOLUTIONS MATH 115: NUMBER THEORY

Problem 1. We compute

2004 = 20 · 99 + 24
99 = 4 · 24 + 3
24 = 3 · 8 + 0

so gcd(2004, 99) = 3.

For (b), we work backwards:

3 = 99 − 4 · 24 = 99 − 4(2004 − 20 · 99) = −4 · 2004 + 81 · 99.

Problem 2. By unique factorization, we may write

a = p_{1}^{e_{1}} … p_{r}^{e_{r}}, b = p_{1}^{f_{1}} … p_{r}^{f_{r}}

where e_{i}, f_{i} ≥ 0 are nonnegative integers and the p_{i} are primes. We know that

p_{1}^{3e_{1}} … p_{r}^{3e_{r}} = a^{3} = b^{2} = p_{1}^{2f_{1}} … p_{r}^{2f_{r}}

so again by unique factorization, we know that 3e_{i} = 2f_{i} for all i.

Since 2 | (2f_{i}) we know 2 | (3e_{i}) so since gcd(2, 3) = 1 (or since 2 is prime and 2 ∤ 3), we know 2 | e_{i}. Let e_{i} = 2c_{i}, and let d = p_{1}^{c_{1}} … p_{r}^{c_{r}}. Then clearly d^{2} = a. Moreover, 3e_{i} = 6c_{i} = 2f_{i} so 3c_{i} = f_{i}. Therefore

d^{3} = p_{1}^{3c_{1}} … p_{r}^{3c_{r}} = p_{1}^{f_{1}} … p_{r}^{f_{r}} = b

as well.

Here is a second proof: like in homework, since a^{3} = b^{2} we know a^{3} | b^{2} hence a | b, so b/a = d ∈ ℤ is an integer. Already d^{3} = b^{3}/a^{3} = b^{3}/b^{2} = b and d^{2} = b^{2}/a^{2} = a^{3}/a^{2} = a.

Problem 3. We first find a solution to

x^{2} − 7x − 6 ≡ 0 (mod 3)

i.e.

x^{2} − x ≡ 0 (mod 3).

This has the solutions x ≡ 0, 1 (mod 3).

Start with r_{0} = 0 and use Hensel’s lemma (Newton’s method). Let f(x) = x^{2} − 7x − 6, so then f′(x) = 2x − 7. Then

f′(0) = −7 ≡ −1 ≢ 0 (mod 3)

so there exists a unique lift of this solution modulo 3^{3} (indeed, to any power 3^{i}). We find

f′(r_{0})^{−1} ≡ (−1)^{−1} ≡ −1 (mod 3)

so

r_{1} = r_{0} − f(r_{0})(f′(r_{0}) mod 3)^{−1} = 0 + (−6) ≡ 3 (mod 9)

Date: July 15, 2004.

and similarly

r_{2} = 3 + (−18) ≡ 12 (mod 27).

We check that indeed 12^{2} − 7(12) − 6 ≡ 0 (mod 27). The other solution x ≡ 1 (mod 3) lifts to x ≡ 22 (mod 27).

For part (b), we note that since f′(0), f′(1) ≢ 0 (mod 3), by Hensel’s lemma we can lift these solutions modulo 3 to a unique solution modulo 3^{5} = 243, so there are exactly two solutions.

Problem 4. Since 365 is odd and 94 is even, n is odd so 2 ∤ n.

We find that 365 ≡ 2 (mod 3) and 94 ≡ 1 (mod 3), so

n ≡ 2^{2004} + 1 (mod 3).

Now 2^{2} = 4 ≡ 1 (mod 3), so

n ≡ 2^{2·1002} + 1 ≡ 1 + 1 ≢ 0 mod 3

so 3 ∤ n.

Since 5 | 365 but 5 ∤ 94, we see 5 ∤ n.

Since 365 ≡ 1 (mod 7) we have

n ≡ 1^{2004} + 94 ≡ 1 + 3 ≢ 0 (mod 7)

so 7 ∤ n.

Finally, 365 ≡ 2 (mod 11). Since gcd(2, 11) = 1, by Fermat’s little theorem, we have 2^{10} ≡ 1 (mod 11). Hence

n ≡ 2^{2000+4} + 6 ≡ 1 · 16 + 6 = 22 ≡ 0 (mod 11)

so 11 | n and 11 is the smallest prime divisor.

Problem 5 (Bonus). We draw a right triangle with interior angle α: the statement arctan(7/2) = α says that the opposite side to the angle α has length 7 and the adjacent side has length 2. By the Pythagorean theorem, this implies that the hypotenuse has length \sqrt{7^{2} + 2^{2}} = \sqrt{53}, hence β = sin(α) = 7/\sqrt{53} = (7/53)\sqrt{53}.

First note that \sqrt{53} is irrational. There are many possible proofs of this fact, one goes as follows: if \sqrt{53} = a/b, with gcd(a, b) = 1, then 53b^{2} = a^{2}, so

ord_{53}(53b^{2}) = 1 + 2 ord_{53}(b) = 2 ord_{53}(a),

a contradiction since an integer cannot both be even and odd. But this also shows that β is irrational, since if (7/53)\sqrt{53} = c/d then \sqrt{53} = (53c)/(7d) ∈ ℚ, a contradiction.