ASSIGNMENT 4 – ELEMENTARY NUMBER THEORY MATH 392

Eyal Goren, November 6, 1998

1. Let B be the group ℤ/nℤ. Except for (a), the questions are for any n!

(a) For n = 12, write the cyclic subgroup generated by every element of B and its order.

(b) Prove that the order of the element k of B is \frac{n}{(n,k)}.

(c) Recall that a cyclic subgroup H of a group G is a subgroup of the form H =< g >, where g ∈ G. A element g′ ∈ G is callled a generator of H if also < g′ >= H. Find the generators of the cyclic subgroups in (a).

(d) Recall that two groups G_{1} and G_{2} are isomorphic, if there exists a bijection f : G_{1} ⟶ G_{2},

satisfying

f(g + g′) = f(g) + f(g′).

Prove that every finite cyclic group is isomorphic to ℤ/nℤ for some n. (By definition: G is a cyclic group if there exists g ∈ G such that G =< g >).

(e) Prove that ℤ/nℤ has precisely ϕ(n) generators, where ϕ is Euler’s function.

(f) How many elements and generators does the subgroup of ℤ/nℤ generated by k have?

(g) Prove that for every ℓ|n the group ℤ/nℤ has a unique subgroup of order ℓ and it is cyclic.

(h) Conclude from the previous questions the formula

n = ∑_{d|n} ϕ(d).

2. Find the solutions for the equation x^{2}+y^{2} = −1 in the rings ℤ/nℤ for n = 2, 3, 4, 5, 6, 7, 8, 9, 10. Formulate some conjecture based on your answer.

3. Prove that every ideal in the ring ℤ[ω] is principal, where ω = \frac{−1+\sqrt{−3}}{2} and ℤ[ω] = {a + bω : a, b ∈ ℤ} .

I suggest you imitate the proof for ℤ[i].

4. Let d ≠ 0, 1, −1, be a square free integer (i.e., if p is a prime then p^{2} |̸d). An element of ℚ(\sqrt{d}) is called an algebraic integer if it is a solution of a polynomial of the form

x^{2} + ax + b,

where a, b are \underline{integers}. Find the algebraic integers of ℚ[i] and ℚ[\sqrt{−3}].