MIDTERM EXAM REVIEW SOLUTIONS MATH 115: NUMBER THEORY

Problem 1. There are many possible solutions to this question. To show that S is not well-ordered, we need to show that there is a subset which does not have a least element; it is certainly enough to show that the set S does not have a least element, or what will also suffice, that there exists a decreasing sequence of elements from S.

We consider the elements 1/\sqrt{p} for p a prime. By Euclid’s theorem, there are infinitely many primes, so the sequence 1/\sqrt{p_{n}} is infinite and strictly decreasing. To conclude, we need to show that 1/\sqrt{p} is irrational. Suppose 1/\sqrt{p} = a/b where a, b ∈ ℤ and gcd(a, b) = 1. Then pa^{2} = b^{2}, so p | b^{2} and thus since p is prime, p | b. Let b = pb′, so then pa^{2} = (pb′)^{2} = p^{2}(b′)^{2}, hence a^{2} = p(b′)^{2}, thus p | a^{2} so p | a. This is a contradiction, since gcd(a, b) = 1.

Problem 2. To find a solution to a congruence modulo 65 = 5 · 13, we first solve the congruence modulo 5 and modulo 13. Indeed, the congruence

x^{2} + 1 ≡ 0 (mod 5)

has only the solutions x ≡ ±2 ≡ 2, 3 (mod 5), and

x^{2} + 1 ≡ 0 (mod 13)

has only the solutions x ≡ ±5 ≡ 5, 8 (mod 13). Now by the Chinese Remainder Theorem, combining each pair of solutions modulo 5 and 13 gives a solution modulo 65, so there are a total of 2 · 2 = 4 solutions modulo 65.

A quick application of the CRT gives x ≡ ±8, ±18 ≡ 8, 18, 47, 57 (mod 65) as the 4 solutions, but any one of them will do.

Problem 3. We note first that gcd(p, q) = 1 since p, q are distinct primes. Therefore by Fermat’s little theorem,

p^{q−1} ≡ 1 (mod q)

hence also

q^{p−1} + p^{q−1} ≡ 1 (mod q)

since q ≡ 0 (mod q). Similarly,

p^{q−1} + q^{p−1} ≡ 1 (mod p).

Therefore

p, q | (p^{q−1} + q^{p−1} − 1)

and so since gcd(p, q) = 1, we have

pq | (p^{q−1} + q^{p−1} − 1)

hence p^{q−1} + q^{p−1} ≡ 1 (mod pq).

Problem 4. Recall that π(x) = #{1 ≤ a ≤ x : a is prime} counts the number of primes up to a real number x ∈ ℝ_{>0}, and that

π(x) ∼ \frac{x}{log x}.

Therefore we can estimate

π(x) ≈ \frac{x}{log x}

hence

π(1000) ≈ \frac{1000}{log 10^{3}} = \frac{1000}{3 log 10} ≈ \frac{1000}{7.5} ≈ 133

and

π(100) ≈ \frac{10^{2}}{2 log 10} ≈ 20.

Therefore the number of primes between 1000 and 100 is

π(1000) − π(100) ≈ 133 − 20 = 113.

Therefore the probability that such a number is prime is ≈ 113/900.

Problem 5. Since (n − 2) | (2n^{2} − 1), we have gcd(n − 2, 2n^{2} − 1) = n − 2. But since gcd(a, c) | gcd(ab, c) for all integers a, b, c by unique factorization, we have

n − 2 = gcd(n − 2, 2n^{2} − 1) | gcd(2(n − 2)(n + 2), 2n^{2} − 1) = gcd(2n^{2} − 8, 2n^{2} − 1).

Now using the fact that the greatest common divisor only depends on linear combinations, we have by subtracting that

gcd(2n^{2} − 8, 2n^{2} − 1) = gcd(−7, 2n^{2} − 1) | 7

so (n − 2) | 7, therefore n − 2 = ±1, ±7, which gives n = −5, 1, 3, 9, and indeed, each of these checks out.

Alternatively, one can use long division to show that (2n^{2} − 1)/(n − 2) = 2n + 4 + 7/(n − 2), which is an integer if and only if (n − 2) | 7, as before.

Problem 6. We easily see that x ≡ 10 (mod 101) is a solution. We now wish to apply Hensel’s lemma. We check that

f′(10) = 2(10) = 20 ≢ 0 (mod 101^{2})

so Newton’s method applies. We next want to compute 20^{−1} (mod 101), and since

20(5) ≡ −1 (mod 101)

we see that 20^{−1} ≡ −5 (mod 101). Therefore by Newton’s method,

r_{1} = r_{0} − f(r_{0})(−5) = 10 + 5(10^{2} + 1) = 515 (mod 101^{2})

is a solution modulo 101^{2}.