Chapter 7

Question 1

Common divisor

Answer 1

Let a, b ⋲ ZZ. We call an integer d a common divisor of a and b provided d|a and d|b.

Question 2

Greatest common divisor

Answer 2

Let a, b ⋲ ZZ. We call an integer d the greatest common divisor
of a and b provided
(1) d is a common divisor of a and b and
(2) if e is a common divisor of a and b, then e ≤ d.
The greatest common divisor of a and b is denoted gcd(a, b)

Question 3

Proposition 36.3

Answer 3

Let a and b be positive integers and let c = a mod b. Then gcd(a, b) = gcd(b, c)

Question 4

Theorem 36.6

Answer 4

Let a and b be integers, not both zero. The smallest positive integer of the form ax + by, where x and y are integers, is gcd(a, b).

Question 5

Definition 36.8

Answer 5

Let a and b be integers. We call a and b relatively prime provided gcd(a, b) = 1

Question 6

Corollary 36.9

Answer 6

Let a and b be integers. There exist integers x and y such that ax + by = 1 if and only if a and b are relatively prime.

Question 7

Proposition 36.10

Answer 7

Let a, b be integers, not both zero. Let d = gcd(a, b). If e is a common divisor of a and b, then e|d.

Question 8

Modular addition, multiplication

Answer 8

Let n be a positive integer. Let a, b ⋲ ZZn. We define

a ⊕ b = (a + b) mod n. and a ⊗ b = (ab) mod n.

Question 9

Modular subtraction

Answer 9

Let n be a positive integer. Let a, b ⋲ ZZn. We define

a ⊖ b tp be the unique x ⋲ ZZn such that a = b ⊕ x

Question 10

Proposition 37.7

Answer 10

Let n be a positive integer and let a, b ⋲ ZZn. Then a ⊖ b = (a - b) mod n.

Question 11

Proposition 37.11

Answer 11

Let n be a positive integer and let a ⋲ ZZn. Suppose a is invertible. If b = a^-1, then b is invertible and a = b^-1. In other words, (a^-1)^-1 = a.

Question 12

Modular division

Answer 12

Let n be a positive integer and let b be an invertible element of ZZn. Let a ⋲ ZZn be arbitrary. Then a ⊘ b is defined to be a ⊗ b^-1. Modular division is only defined when b is invertible

Question 13

Invertible elements of ZZn

Answer 13

Let n be a positive integer and let a ⋲ ZZn . Then a is invertible if and only if a and n are relatively prime.

Question 14

Fundamental Theorem of Arithmetic

Answer 14

Let n be a positive integer. Then n factors into a product of primes. Furthermore, the factorization of n into primes is unique up to the order of the primes.

Question 15

Lemma 39.2

Answer 15

Suppose a, b, p ⋲ ZZ and p is a prime. If p|ab, then p|a or p|b.

Question 16

Infinitude of primes

Answer 16

There are infinitely many prime numbers.