KMB, 27/10/99

M3/4P14 Elementary Number Theory—Problem Sheet 2

This is assessed coursework. Please hand in solutions to the starred questions (i.e., to questions 1, 3, 4, 7 and 9) at the end of the lecture on Wednesday 10th November.

1^{∗})

(a) Solve 4x ≡ 2 mod 9 by brute force—that is, go through all nine choices of x mod 9 and see which ones work.

(b) Find integers λ and μ such that 4λ + 9μ = 1 (guessing is fine; Euclid will also work). Deduce what the inverse of 4 in the group (ℤ/9ℤ)^{×} is [that is, find some integer t such that 4t ≡ 1 mod 9].

(c) Now solve 4x ≡ 2 mod 9 by multiplying by this inverse of 4. [Don’t forget to check your solution works]

2) Using any method you like, solve each of the following equations:

(a) 4x ≡ 6 mod 8 (b) 4x ≡ 6 mod 9 (c) 4x ≡ 6 mod 10

3^{∗}) Find an integer x such that x ≡ 5 mod 7 and x ≡ 7 mod 5. Now find all such integers.

4^{∗}) (tricky) Does there exist an integer x such that x ≡ 5 mod 8 and x ≡ 3 mod 10? What is the general solution to these equations? Does there exist an integer y such that y ≡ 6 mod 8 and y ≡ 3 mod 10?

5) Think about solving simultaneously the equations x ≡ a mod m and x ≡ b mod n. By CRT there is always a solution if hcf(m, n) = 1. If you did Q4 then you’ll know that the situation is more complex in the non-coprime case. Make a conjecture about when the equations are simultaneously solvable; make a conjecture about the general form of the solution [the solution, if one exists, will be of the form x ≡ A mod M but what is M?]. Now prove all your conjectures. If you manage this question then you’re really doing pretty well.

6) Find three positive integers a, b, c, such that no pair are coprime, and yet no prime divides all three.

7^{∗}) How many elements does (ℤ/8ℤ)^{×} have? Take any element in (ℤ/8ℤ)^{×} and square it—now try another. In fact, square every element in (ℤ/8ℤ)^{×}. What do you notice? [Bonus question: what is the group (ℤ/8ℤ)^{×}?]

8) If you feel confident about abelian groups, try and work out what the following groups are: (ℤ/9ℤ)^{×}, (ℤ/10ℤ)^{×}, (ℤ/12ℤ)^{×}. One way of getting a handle on small groups like this is to work out their order, and then to start squaring and cubing the elements to see what’s going on. Recall that any finite abelian group is the product of cyclic groups, so these things can’t be too bad.

9^{∗}) Let n be an integer. Prove that n^{5} ≡ n^{3} mod 24. Hint: there are several ways to do this. One particularly arduous one would be to check it for all 24 cases. A much nicer method would involve reducing the problem to some smaller ones, (the mod 24 world is the “product” of which two smaller worlds?) and then using theorems from the course; there are also other approaches. There’s frequently more than one way to skin a cat in number theory.