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 \in \mathbb{Z}\) and \(b \in \mathbb{Z} \setminus \{0\}\text{.}\) We say that \(a\) is divisible by \(b\text{,}\) or \(b\) divides \(a\text{,}\) denoted by

\begin{equation*} b \mid a\text{,} \end{equation*}

if there exists \(m \in \mathbb{Z}\) such that \(a = mb\text{.}\)

If \(b\) is not divisible by \(a\text{,}\) then we write \(b \nmid a\text{.}\)

We say that the natural number \(p\) is a prime number if the only natural numbers that divide \(p\) are \(1\) and \(p\text{.}\)

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

\begin{equation*} \gcd(a,b)\text{,} \end{equation*}

is the largest integer that divides both numbers.

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

There are a number of ways to determine the GCD of two numbers \(a\) and \(b\text{:}\)

  • Listing all factors of \(a\) and \(b\text{,}\) then finding the largest one they have in common;
  • Writing out the prime factorizations of \(a\) and \(b\text{,}\) 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