KMB, 17/11/99

M3/4P14 Elementary Number Theory—Problem Sheet 3

Some of this is assessed coursework. Please hand in solutions to the starred questions (i.e., to questions 2, 6, 7, 9, 12) at the end of the lecture on Monday November 29th.

1) Let f and g be multiplicative functions. Define a new function f ∗ g by

(f ∗ g)(n) = ∑_{d|n} f(d)g(n/d),

where the sum is, as usual, over the positive divisors of n. Prove that (f ∗ g) is also multiplicative.

Remark: The function f ∗ g is called the convolution of f and g, and people who have seen this word used for continuous functions will see that this is some kind of algebraic analogue of the usual definition.

2^{∗}) Let d(n) denote the number of (positive) divisors of n, and let σ(n) denote their sum. If n = ∏_{i=1}^{r} p_{i}^{e_{i}} with p_{1}, p_{2},… p_{r} distinct primes, then show that

a) d(n) = ∏_{i}(e_{i} + 1)

b) σ(n) = ∏_{i} \frac{p_{i}^{e_{i}+1}−1}{p_{i}−1}

3) For which n ≥ 1 is ϕ(n) a multiple of 2? And for which n ≥ 1 is ϕ(n) a multiple of 3?

[ If you want more practice doing exercises about multiplicative functions, then Baker’s book has got some trickier ones.]

4) Let m > 2 be an integer, and assume that there is a primitive root, say a, mod m.

a) Briefly explain (two or three sentences will do) why every element of (ℤ/mℤ)^{×} can be uniquely expressed as a^{t} mod m, for some integer t with 0 ≤ t < ϕ(m).

b) Let s be an integer with 0 ≤ s < ϕ(m). Explain how to write (a^{s})^{2} as a^{t} with 0 ≤ t < ϕ(m). (two cases!)

c) Explain why there are exactly two solutions mod m to the equation

X^{2} ≡ 1 mod m.

[Note the word “exactly”, which means that if you only prove that there are at least 2 solutions, or at most 2 solutions, then you haven’t done the question.]

5) In this question, we’ll work out exactly for which m > 0 there is a primitive root mod m.

a) Show that every positive integer m satisfies one of the following conditions: (A) m = 1, 2, or 4. (B) m = p^{t}, t ≥ 1 and p an odd prime. (C) m = 2^{t}, t ≥ 3. (D) m = 2p^{t} with t ≥ 1 and p an odd prime. (E) m = ab with a, b coprime integers, both at least 3.

Once you have done this, the strategy is clear: deal with each case separately. We have done some of the cases already. Every integer satisfying condition (A) has a primitive root—just check. In lectures, we showed that everything in case (B) has a primitive root (Theorem 4.10), and nothing in case (C) does (Theorem 4.12). This leaves us with (D) and (E).

b) Let p be an odd prime, let t ≥ 1 be an integer, and let a be a primitive root mod p^{t}. Show that a is a primitive root mod 2p^{t}. Hence case (D) is dealt with.

c) Say m = ab with a, b coprime and both at least 3. Use the Chinese Remainder Theorem to deduce that there are integers n_{++}, n_{+−}, n_{−+} and n_{−−} such that

n_{++} ≡ +1 mod a and n_{++} ≡ +1 mod b,
n_{+−} ≡ +1 mod a and n_{+−} ≡ −1 mod b,
n_{−+} ≡ −1 mod a and n_{−+} ≡ +1 mod b,
n_{−−} ≡ −1 mod a and n_{−−} ≡ −1 mod b.

Now explain briefly why all four of these integers are distinct mod m, and why the square of any one of them is 1 mod m.

d) Deduce, using Q4, that if m = ab is as in part (c), then there is no primitive root mod m. Hence case (E) is also dealt with.

6^{∗}) What are all the primitive roots mod 9? Mod 10? Mod 12?

7^{∗}) Solve the following equations. (No marks will be given for just writing down the answers with no working—we all know that something like Mathematica/Maple can just do (some of) these questions by brute force: the trick is to work out how to work them out without a computer, instead using results from the course and some brain power.)

a) Find an integer a with 0 ≤ a ≤ 6 and a ≡ 2^{1000000} mod 7.

b) Find an integer b with 0 ≤ b ≤ 10 and b ≡ 1999^{1999} mod 11.

c) Find an integer c with 0 ≤ c ≤ 14 and c ≡ 9^{1000000} mod 15.

8) If n > 1 and n is not a prime, then prove that (n − 1)! is not congruent to −1 mod n. Hence Wilson’s theorem gives a primality test, that is, if n > 1 is an integer, then we can test to see whether n is prime by working (n − 1)! and seeing if it’s −1 mod n. Comment on its efficiency compared to, say, trial division.

9^{∗}) How’s your logic? Read the statements of Wilson’s theorem and Fermat’s little theorem, and Q8 too. Any answer that obviously contains steps that were done on a computer is worthless—the point is that you can do all these questions without one.

a) Prove that if p is an odd prime, then 2^{p−1} ≡ 1 mod p.

b) Let n = 651693055693681. I just checked on a computer that 2^{n−1} ≡ 1 mod n. Can we deduce, just from this information, that n is prime?

c) Let m = n + 28 = 651693055693709. I just checked on a computer that 2^{m−1} ≡ 613609515736831 mod m. Can we deduce, just from this information, that m is not prime?

d) I just worked out (m − 1)! mod m. What did I get?

10) Let a ∈ ℤ have order k mod m. Let h ≥ 1 be an integer. Prove that a^{h} has order k mod m if and only if hcf(h, k) = 1.

11) Let m be 2 × 5^{1999}. Prove that 3 is a primitive root mod m. This is actually a bit of a challenge!

12^{∗})

(a) Find infinitely many solutions to n = 3ϕ(n).

(b) Prove that n = 4ϕ(n) has no solutions.

(c) Is there an integer t > 4 such that n = tϕ(n) has a solution?

(d) Is there an integer n such that n > 1999ϕ(n)? Remark: (c) and (d) are quite challenging—but you will not be penalised too

heavily if you cannot do them at all, so don’t worry. In fact, rather the opposite is true—I will be impressed by people who manage to do either of them.