ASSIGNMENT 3 – ELEMENTARY NUMBER THEORY MATH 392

Eyal Goren, November 6, 1998

In this assignment (and through the course) a “group” means an “abelian group”. Answer the following questions:

1. Let n ∈ ℕ and write n in the usual decimal expansion:

n = a_{k} ⋯ a_{2}a_{1}.

That is, the a_{i}’s are just the digits of n. Use the technique of congruences to prove the following:

(A) n is divisible by 3 if and only if a_{1} + a_{2} + ⋯ a_{k} is divisible by 3. (E.g.: 231231 is divisible by 3 and indeed 2 + 3 + 1 + 2 + 3 + 1 = 12 is divisible by 3).

(B) n is divisible by 11 if and only if −a_{1} + a_{2} − a_{3} + ⋯ + (−1)^{k}a_{k} is divisible by 11. (E.g.: 231231 is divisible by 11 and indeed −2 + 3 − 1 + 2 − 3 + 1 = 0 is divisible by 11).

(C) n is divisible by 7 if and only if the number a_{k} ⋯ a_{3}a_{2} − 2a_{1} is divisible by 7. (E.g.: 23107 is divisible by 7. The criterion says it is enough to check that 2310 − 2 · 7 = 2296 is divisible by 7. Iterating, it is enough to prove that 229 − 2 · 6 = 217 is divisible by 7. Iterating, it is enough to prove 21 − 2 · 7 = 7 is divisible by 7 and it is !)

2. Prove that every year we must have “Friday the 13-th” (Assume that every month contains precisely 30 days).

3. Do exercise (i) on page 25 in Baker’s: :Find an integer x such that

2x ≡ 1 (mod 3), 3x ≡ 1 (mod 5), 5x ≡ 1 (mod 7).

4. Let G be a group. Prove: (i) −(−x) = x; (ii) −(nx) = n(−x) for n ∈ ℕ , where nx = x + x + ⋯ + x (n times).

5. Let G be a group and H_{1}, H_{2} subgroups.

(A) Prove that

H_{1} + H_{2} = {h_{1} + h_{2} : h_{1} ∈ H_{1}, h_{2} ∈ H_{2}}

is a subgroup.

(B) Prove that H_{1} ∩ H_{2} is a subgroup.

(C) Give an example where H_{1} ∪ H_{2} is not a subgroup.

(D) Let H be a nonempty subset of G such that

x, y ∈ H ⇒ x − y ∈ H.

Prove that H is a subgroup.

6. (A) Define the least common multiple of x, y ∈ ℕ to be a number f such that x|f, y|f and if x|h, y|h then f|h. Prove that such a number exists and unique. It is denoted lcm(x, y).

Prove that we have: lcm(x, y) = xy/gcd(x, y).

(B) consider the subgroups xℤ and yℤ of ℤ. Prove that

xℤ ∩ yℤ = fℤ, xℤ + yℤ = dℤ,

where d = gcd(x, y), f = lcm(x, y).