ASSIGNMENT 2 – ELEMENTARY NUMBER THEORY MATH 392

Eyal Goren, November 6, 1998

Answer the following questions:

1. By a suitable variation on Euclid’s proof, prove that there are infinitely many primes p, such that p ≡ 3 (mod 4).

2. Prove that e, defined as

e = 1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + ⋯,

is an irrational number.

3. Using the methods of the lecture, define the g.c.d. of n natural numbers a_{1}, ⋯, a_{n} as the unique natural number d such that d|a_{i} for every i and if e|a_{i} for every i then e|d. Lets denote is by

(a_{1}, ⋯, a_{n}).

Prove that it exists and unique. Show also that there exists integers x_{1}, ⋯, x_{n} such that

x_{1}a_{1} + ⋯ + x_{n}a_{n} = (a_{1}, ⋯, a_{n}).

Prove the identity

(a_{1}, ⋯, a_{n}) = ((a_{1}, ⋯, a_{n−1}), a_{n}).

Now do exercise (ii) on page 7 in Baker’s book:

“ Find integers x, y, z such that 35x + 55y + 77z = 1.”

4. (a) Prove that for every prime p and every 1 ≤ r ≤ p − 1, p| (\begin{matrix}p \\ r \end{matrix}) .

(b) Let f be a numerical polynomial of degree n. Let p be a prime greater then n. Prove that p|(f(p) − f(0)).

5. Compute a formula for

1^{4} + 2^{4} + ⋯ + (x − 1)^{4}.

6. Evaluate ∑_{d|n} μ(n/d)σ(d).

7. Do exercise (i) on page 16 of Baker’s book:

“ Evaluate ∑_{d|n} μ(d)σ(d) in terms of the distinct prime divisors of n.”

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ ϕ(n) & 1 & 1 & 2 & 2 & 4 & 2 & 6 & 4 & 6 & 4 & 10 & 4 & 12 & 6 & 8 \\ μ(n) & 1 & -1 & -1 & 0 & -1 & 1 & -1 & 0 & 0 & 1 & -1 & 0 & -1 & 1 & 1 \\ d(n) & 1 & 2 & 2 & 3 & 2 & 4 & 2 & 4 & 3 & 4 & 2 & 6 & 2 & 4 & 4 \\ σ(n) & 1 & 3 & 4 & 7 & 6 & 12 & 8 & 15 & 13 & 18 & 12 & 28 & 14 & 24 & 24 \end{matrix}

\begin{matrix}n & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\ ϕ(n) & 8 & 16 & 6 & 18 & 8 & 12 & 10 & 22 & 8 & 20 & 12 & 18 & 12 & 28 & 8 \\ μ(n) & 0 & -1 & 0 & -1 & 0 & 1 & 1 & -1 & 0 & 0 & 1 & 0 & 0 & -1 & -1 \\ d(n) & 5 & 2 & 6 & 2 & 6 & 4 & 4 & 2 & 8 & 3 & 4 & 4 & 6 & 2 & 8 \\ σ(n) & 31 & 18 & 39 & 20 & 42 & 32 & 36 & 24 & 60 & 31 & 42 & 40 & 56 & 30 & 72 \end{matrix}

\begin{matrix}n & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 \\ ϕ(n) & 30 & 16 & 20 & 16 & 24 & 12 & 36 & 18 & 24 & 16 & 40 & 12 & 42 & 20 & 24 \\ μ(n) & -1 & 0 & 1 & 1 & 1 & 0 & -1 & 1 & 1 & 0 & -1 & -1 & -1 & 0 & 0 \\ d(n) & 2 & 6 & 4 & 4 & 4 & 9 & 2 & 4 & 4 & 8 & 2 & 8 & 2 & 6 & 6 \\ σ(n) & 32 & 63 & 48 & 54 & 48 & 91 & 38 & 60 & 56 & 90 & 42 & 96 & 44 & 84 & 78 \end{matrix}

\begin{matrix}n & 46 & 47 & 48 & 49 & 50 & 51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 \\ ϕ(n) & 22 & 46 & 16 & 42 & 20 & 32 & 24 & 52 & 18 & 40 & 24 & 36 & 28 & 58 & 16 \\ μ(n) & 1 & -1 & 0 & 0 & 0 & 1 & 0 & -1 & 0 & 1 & 0 & 1 & 1 & -1 & 0 \\ d(n) & 4 & 2 & 10 & 3 & 6 & 4 & 6 & 2 & 8 & 4 & 8 & 4 & 4 & 2 & 12 \\ σ(n) & 72 & 48 & 124 & 57 & 93 & 72 & 98 & 54 & 120 & 72 & 120 & 80 & 90 & 60 & 168 \end{matrix}