myLearning

Step 21: Proofs and discrete maths

Divisibility and modular arithmetic

Step 21 · Proofs and discrete maths topics

Use divisibility and the division algorithm, find greatest common divisors with Euclid's algorithm, and calculate with congruences, the arithmetic of remainders.

Divisibility

a divides b, written a | b, when b = ak for some integer k. The division algorithm says any integer b can be written as b = qa + r with 0 ≤ r < a: a quotient and a remainder.

Example: The division algorithm

Divide 47 by 6.

  1. 6 × 7 = 42, and 47 − 42 = 5.

Answer47 = 7 × 6 + 5: quotient 7, remainder 5

Example: A negative number

Divide −17 by 5.

  1. The remainder must be between 0 and 4.
  2. −17 = (−4) × 5 + 3.

AnswerQuotient −4, remainder 3

Greatest common divisors

gcd(a, b) is the largest integer that divides both a and b. Euclid's algorithm finds it by repeated division: gcd(a, b) = gcd(b, r), where r is the remainder of a ÷ b, until the remainder is 0.

Example: Euclid's algorithm

Find gcd(252, 105).

  1. 252 = 2 × 105 + 42.
  2. 105 = 2 × 42 + 21.
  3. 42 = 2 × 21 + 0.

Answer21

Example: Bézout's identity

Write 21 as a combination of 252 and 105.

  1. Work back up: 21 = 105 − 2 × 42, and 42 = 252 − 2 × 105.
  2. So 21 = 105 − 2(252 − 2 × 105), which is 5 × 105 − 2 × 252.

Answer21 = 5 × 105 − 2 × 252

Congruences

a ≡ b (mod n) means n divides a − b: a and b leave the same remainder when divided by n. Congruences can be added and multiplied like equations, so you can reduce numbers first.

Example: Clock arithmetic

It is 9 o'clock. What time is it 50 hours later?

  1. 9 + 50 = 59, and 59 ≡ 11 (mod 12).

Answer11 o'clock

Example: A big power

Find the remainder when 2¹⁰⁰ is divided by 7.

  1. 2³ = 8 ≡ 1 (mod 7).
  2. 2¹⁰⁰ = (2³)³³ × 2 ≡ 1 × 2.

Answer2

Example: Dividing by 9

Why is a number divisible by 9 exactly when its digit sum is?

  1. 10 ≡ 1 (mod 9), so every power of 10 is ≡ 1.
  2. So a number is congruent to the sum of its digits mod 9.

AnswerThey leave the same remainder when divided by 9

Try it yourself

Work each one on paper first, then open the answer to check.

  1. Find the quotient and remainder of 100 ÷ 7.

    Show answer

    14, remainder 2

  2. Find gcd(48, 18).

    Show answer

    6

  3. Are 35 and 64 coprime?

    Show answer

    Yes: their gcd is 1

  4. What is 17 mod 5?

    Show answer

    2

  5. Find the remainder when 3²⁰ is divided by 8.

    Show answer

    1

  6. Is 123,456 divisible by 9?

    Show answer

    No: its digit sum is 21

What next?