School of Mathematical and Prof.

Pablo Rosero
Computational Sciences & Christian Chávez
Abstract Algebra
Problem Set 1
Basic Arithmetic

Lesson 1 & 2
1. For each of the following pairs of integers a and b, determine their greatest
common divisor, their least common multiple, and write their greatest
common divisor in the form ax + by for some integers x and y.

(a) a = 792, b = 275

(b) a = 507885, b = 60808

2. Prove that if n is composite then there are integers a and b such that n
divides ab but n does not divide either a or b.

3. If p is a prime, prove that there do not exist nonzero integers a and b such
√
that a2 = pb2 . (Why this proves p is not a rational number.)

4. Write down explicitly all the elements in the residue classes of Z/18Z.

5. Suppose a = an 10n + an−1 10n−1 + · · · + a1 10 + a0 is any positive integer.

Show that a ≡ an + an−1 + · · · + a1 + a0 (mod 9). (Note that this is the
usual arithmetic rule that the remainder after division by 9 is the same as
the sum of the decimal digits mod 9. In particular, an integer is divisible
by 9 if and only if the sum of its digits is divisible by 9).

6. Compute the remainder when 37100 is divided by 29.

7. Prove that the squares of the elements in Z/4Z are just 0 and 1.

8. Let a, b ∈ Z. Prove that a2 + b2 never leaves a remainder of 3 when

divided by 4. (Hint: use the previous exercise.)

9. Prove that the equation x2 + y2 = 3z2 has no solutions for x, y, z ∈ Z.

10. Prove that if a, b ∈ (Z/nZ)× , then a · b ∈ (Z/nZ)× .

11. Let n ∈ Z, n > 1, and let a ∈ Z with 1 ≤ a ≤ n. Prove if a and n are not
relatively prime, there exists an integer b with 1 ≤ b < n such that ab ≡ 0
(mod n) and deduce that there cannot be an integer c such that ac ≡ 1
(mod n).
12. Let n ∈ Z, n > 1, and let a ∈ Z with 1 ≤ a ≤ n. Prove that if a and n
are relatively prime then there is an integer c such that ac ≡ 1 (mod n).
(Use the fact that the g.c.d. of two integers is a Z-linear combination of
the integers.)

13. Conclude from the previous two exercises that (Z/nZ)× is the set of
elements ā of Z/nZ with ( a, n) = 1 and hence prove Proposition 4 .
Verify this directly in the case n = 12.

1
14. (a) Prove that if n is squarefree (i.e., n > 1 and n is not divisible by the
√
square of any prime), then n is irrational.
√
(b) Prove that 3 2 is irrational.

15. Let a and b be nonzero integers and let d = ( a, b). Prove that a/d and b/d
are relatively prime.

16. Let m, r, r ′ ∈ Z. Prove that if (r, m) = 1 = (r ′ , m), then (rr ′ , m) = 1.

17. Assume that d = sa + tb is a Z-linear combination of integers a and b.

Find infinitely many pairs of integers (sk , tk ) with d = sk a + tk b.

18. If a and b are relatively prime and if each divides an integer n, then their
product ab also divides n.

19. Let a, b, c ∈ Z with a > 0. Prove that a(b, c) = ( ab, ac). (One must assume
that a > 0 lest a(b, c) be negative.)

20. A Pythagorean triple is a 3-tuple ( a, b, c) of positive integers for which

a2 + b2 = c2 .
A Pythagorean triple is called primitive if gcd( a, b, c) = 1. (Definition. A
common divisor of nonzero integers a1 , a2 , . . . , an is an integer c such that
c | ai for all i ∈ {1, . . . , n}. The largest of the common divisors is called its
greatest common divisor.)

(a) Consider a complex number z = q + ip, where q > p are positive

integers. Prove that
q2 − p2 , 2qp, q2 + p2

is a Pythagorean triple by showing that z2 = |z|2 . (One can prove

that every primitive Pythagorean triple ( a, b, c) is of this type.)

(b) Show that the Pythagorean triple (9, 12, 15) (which is not primitive)
is not of the type given in part (a).

21. Let X and Y be finite sets. Show that there is a bijection f : X → Y if and
only if | X | = |Y |. (By definition, a set is finite if it is empty or if it can
be put in a one-to-one correspondence with [k ] = {1, 2, . . . , k }, for some
integer k ≥ 1.)

22. (Pigeonhole Principle) If X and Y are finite sets with the same number of
elements, show that the following conditions are equivalent for a function
f : X → Y.

(a) f is bijective

(b) f is injective

(c) f is surjective

23. (a) Let f : X → Y be a function, and let (Si )i∈ I be a family of subsets of
X. Prove that !
[ [
f Si = f ( Si )
i∈ I i∈ I

2
 (b) If S1 and S2 are subsets of a set X, and if f : X → Y is any function,
prove that f (S1 ∩ S2 ) ⊆ f (S1 ) ∩ f (S2 ). Give an example in which
f ( S1 ∩ S2 ) ̸ = f ( S1 ) ∩ f ( S2 ) .

(c) If S1 and S2 are subsets of a set X, and if f : X → Y is an injection,

prove that f (S1 ∩ S2 ) = f (S1 ) ∩ f (S2 ).

24. Let f : X → Y be a function.

(a) If ( Bλ )λ∈Λ is a family of subsets of Y, prove that

! !
f −1 f −1 ( Bλ ) f −1 f −1 ( Bλ ) .
[ [ \ \
Bλ = and Bλ =
λ∈Λ λ∈Λ λ∈Λ λ∈Λ

 
(b) If B ⊆ Y, prove that f −1 B∁ = f −1 ( B)∁ , where B∁ denotes the
complement of B respect to Y.

25. Let f : X → Y be a function. Define a relation on X by x ≡ x ′ if f ( x ) =

f ( x ′ ). Prove that ≡ is an equivalence relation. (If x ∈ X and f ( x ) = y, the
equivalence class [ x ] is usually denoted by f −1 (y), the inverse image of
{y}.)