Skip to main content

Section 1.3 Integers and Divisibility

For completeness we restate here the definition of divisibility and the Division Algorithm.

Definition 1.3.1. Divisibility and Primes.

Let a∈Z and b∈Z∖{0}. We say that a is divisible by b, or b divides a, denoted by

b∣a,

if there exists m∈Z such that a=mb.

If b is not divisible by a, then we write b∤a.

We say that the natural number p is a prime number if the only natural numbers that divide p are 1 and p.

Find \(q\) and \(r\) that satisfy Theorem 1.3.2 for the following pairs of numbers \(a\) and \(b\text{:}\)

  1. \(\displaystyle a = 140, b = 22\)
  2. \(\displaystyle a = 22, b = 140\)
  3. \(\displaystyle a = 735, b = 21\)
Definition 1.3.4. GCD.

Given integers a and b not both zero, their greatest common divisor, denoted by

gcd(a,b),

is the largest integer that divides both numbers.

We say that a and b are relatively prime if gcd(a,b)=1.

There are a number of ways to determine the GCD of two numbers a and b:

  • Listing all factors of a and b, then finding the largest one they have in common;
  • Writing out the prime factorizations of a and b, then collecting all common prime factors;
  • The Euclidean Algorithm (repeated division).

Apply the three techniques above to compute \(\gcd(220,360)\text{.}\)

Answer

The GCD is 20.

If \(a\) and \(b\) are nonzero integers and \(k\) is an integer, show that \(\gcd(a,b) = \gcd(a-kb,b)\text{.}\)

Find a pair of integers \(x\) and \(y\) such that

\begin{equation*} 13x + 11y = 2\text{.} \end{equation*}

Then explain why the equation \(13x + 11y = 2\) has infinitely many solutions. Can you characterize all such solutions?

Prove that the equation

\begin{equation*} 14x - 35y = 9 \end{equation*}

has no integer solutions.

Let \(a, b, d, \in \mathbb{N}\text{.}\) Prove that \(ax + by = d\) has integer solutions \(x\) and \(y\) if and only if \(\gcd(a,b) \mid d\text{.}\)

Let \(m,a,b \in \mathbb{N}\text{.}\) Using Theorem 1.3.7, prove that if \(m \mid ab\) and \(\gcd(a,m) = 1\text{,}\) then \(m \mid b\text{.}\)

Solutions Solutions to Selected Checkpoints

Checkpoint 1.3.5. Compute the GCDs.
Solution