Week 1

Question 1

Define the terms:

1. divisor
2. prime number
3. composite number

Answer 1

Let a, b ∈ ɴ

1. if a divides b, then a is a divisor of b (and b is a multiple of a)
2. if a has only two distinct divisors (which will be 1 and a), then a is prime
3. if a has more than two distinct divisors, then a is composite

Question 2

How do you determine whether one natural number divides another?

Answer 2

If a divides b then there exists some c ∈ ɴ such that b = ac

Question 3

Use the definition of a divisor to prove the following basic results about divisibility.

Let a, b, q ∈ ɴ.

1. Show that if q | a then q | ab
2. Show that if a | b and a | c, then a | (b + c)

Answer 3

1. 1. If q | a, then there exists some c ∈ ɴ such that a = qc
   2. Multiplying both sides by b, we see that ab = qcb
   3. Associating terms to highlight the result, we have ab = q(bc), which is to say that q | ab
2. 1. If a | b, then there exists some k₁ ∈ ɴ such that b = ak₁
   2. Similarly, if a | c, then there exists some k₂ ∈ ɴ such that c = ak₂
   3. In this case, b + c = ak₁ + ak₂ = a(k₁ + k₂)
   4. Thus we see that a | (b + c)

Question 4

State the Fundamental Theorem of Arithmetic

Answer 4

Every natural number can be expressed as a product of primes:

Let n ∈ ɴ. Then we can write n in the form

n = p₁^i₁p₂^i₂…p_k^i_k

where p₁, p₂, …, p_k ∈ ɴ are distinct primes and i₁, i₂, …, i_k ∈ ɴ.

Furthermore, there is only one such representation (aside from reordering the primes) for each number.

Question 5

Define the terms:

1. greatest common divisor
2. lowest common multiple
3. coprime (using a prior definition here)

Answer 5

1. gcd(a, b) is the largest n ∈ ɴ such that n | a and n | b
2. lcm(a, b) is the smallest n ∈ ɴ such that a | n and b | n
3. if gcd(a, b) = 1 then a and b are coprime

Question 6

Apply the Euclidean Algorithm to find the greatest common divisor of [two natural numbers]

Question 7

Apply the Extended Euclidean algorithm to natural numbers a, b in order to find integers s, t with as + bt = gcd(a, b)

Question 8

Is the number 1 composite or prime?

Why? (Refer to definitions of composite and prime)

Answer 8

Neither, because it does not have two distinct divisors, or more than two distinct divisors