Question 1

This question tests your knowledge of what constitutes a group. Let n be a composite number. Let X = {1, 2, . . . , n − 1}.

(a) Let x ∈ X. Show that if there are integers a, b such that ax + bn = 1, then gcd(x, n) = 1.

(b) Let x ∈ X. Show that if gcd(x, n) 6= 1 then ax ≡ 1 (mod n) has no solution for any integer a.

(c) Show that there is at least one element x ∈ X, such that gcd(x, n) 6= 1.

(d) Let ∗ be multiplication modulo n. That is, for x, y ∈ X, x ∗ y = xy (mod n). Prove that (X, ∗) is not a group.