This topic is about both major arithmetic operations, addition/subtraction and multiplication/division.  It lies at the heart of so much of our basic understanding of numbers. In a certain sense, it is the source of the deep complexity that we find in the theory of numbers.  If you’ve taken number theory, you’ve already learned a *lot* about this relationship. But even if you haven’t, you already have a strong intuitive sense of the basic ideas of divisibility.

I don’t just want you to know about divisibility. I want you to feel it. In your bones!

Prof. Reitz

Let’s start with the basic idea.

Question: What does it mean to say that “$a$ goes into $b$” or “$a$ goes into $b$ evenly”? NOTE: It’s assumed when we say this that $a$ and $b$ are integers.

Multiple and Divisor. We use several different types of language to describe this situation, depending on which number we are focussing on. If “$a$ goes into $b$ evenly,” then we can:

  • Describe $b$ in this scenario as a “multiple of $a$”
    • Definition. $b$ is a multiple of $a$ means you can multiply $a$ by an integer and get $b$.
  • Describe $a$ in this scenario as a “divisor of $b$”
    • Definition. $a$ is a divisor of $b$ means you can multiply $a$ by an integer and get $b$. Sometimes we also say “$a$ divides $b$”.

Exercise. Describe the relationship between 5 and 35, first in terms of multiple and then in terms of divisor.

Question. What are the divisors of $12$? List them.

Question. What are the multiples of $7$? List them.

Exercise (Group).

  • Write a definition for the GCD of an integer (what does GCD stand for?)
  • Write a definition for the LCM of an integer (what does LCM stand for?)

Exercise. Reduce the following fractions. For each one, what did you cancel out of the numerator and denominator?

  • $\frac{25}{10}$
  • $\frac{14}{22}$
  • $\frac{12}{60}$
  • $\frac{13}{33}$
  • $\frac{1147}{899}$

NOTE: unless the numerator and denominator are relatively small, it’s not always easy to tell if a fraction is reduced! If classroom instruction always focuses on single-digit numerator/ denominator, we get the impression we can always tell “just by looking.”

Exercise. Find the GCD of each pair of numbers:

  • 10, 25
  • 14, 22
  • 60, 12
  • 13, 33
  • 1147, 899

Linear Combinations

Example: Rosa wants to buy a piece of candy from Jamal for ten cents.  Rosa only has quarters.  Jamal checks his pocket and finds he has only dimes.  Explain how Rosa can buy the candy from Jamal.

Definition.  A linear combination of two numbers is a sum of multiples of those numbers. In symbols, a linear combination of integers $a$ and $b$ is an expression of the form $n\cdot a + m\cdot b$, where $n$ and $m$ are integers.

You can create all linear combinations of, for example, 25 and 10, by starting at 0 and repeatedly adding or subtracting either 25 or 10 at each step.

Exercise. Create the smallest possible positive number as a linear combination of the two numbers:

  • 10, 25
  • 14, 22
  • 60, 12
  • 13, 33
  • 1147, 899

(Desmos demo here on multiples of a number, linear combinations of a number).

Fact. The linear combinations of two integers a and b are exactly the multiples of the GCD of a and b.

Fact. The GCD of a and b can be written as a linear combination of a and b.

How do we do this?

EXAMPLE: Given the numbers 258 and 60, how do we:

  • Find the GCD of 258 and 60?
  • Write the GCD of 258 and 60 as a linear combination of 258 and 60?

The Euclidean Algorithm

This is important because it is an actual set of steps (NOT “guess-and-check”) that will give you the GCD of any two numbers.

Example. Find the GCD of 258 and 60. Write the GCD as a linear combination of 258 and 60.

Example (class). Find the GCD of 22 and 14, and write the GCD as a linear combination of 22 and 14.

The Euclidean algorithm works in stages. Each stage consists of 4 steps:

  1. Start with two numbers, a larger one and a smaller one.
  2. Divide the smaller number into the bigger number (use division with remainder), let r be the remainder.
  3. Write down an equation giving r as a linear combination of the two numbers.
  4. Now go back to step 1, replacing the larger number with the number r found in step 2.

Repeat until you reach a remainder of 0. The previous stage (the last nonzero remainder) is the GCD of the original two numbers.

Now work backwards, starting with the GCD. In each stage, use the equation from step 3 to write the GCD in terms of the two numbers in step 1.

Example: Find the GCD of 2964 and 288. Write the GCD as a linear combination of 2964 and 288.

Exercise: Find the GCD of 710 and 170 using the Euclidean Algorithm.

Exercise: Find the GCD of 1147 and 899.

Exercise. Find GCD(10049,1190)