Modular arithmetic and divisibility tests

Modular arithmetic and divisibility tests

Spec 5.3 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • a≡b(modn)a\equiv b\pmod n means nn divides a−ba-b: aa and bb leave the same remainder on division by nn.
  • Congruences can be added, subtracted, multiplied and raised to powers: reduce at each stage.
  • Divisibility: by 22, 55, 1010 use the last digit; by 44 the last two digits.
  • By 33 and 99 use the digit sum; by 66 test both 22 and 33.
  • By 1111 use the alternating digit sum, starting from the units digit.

Divisor 2, 5, 10

  • Last digit

Divisor 4

  • Last two digits

Divisor 3, 9

  • Digit sum

Divisor 11

  • Alternating digit sum

Congruence and its properties

Two integers are congruent modulo nn when their difference is a multiple of nn.

Two integers aa and bb are congruent modulo nn, written a≡b(modn)a\equiv b\pmod n, when nn divides a−ba-b.

Every integer is congruent to exactly one value in {0,1,…,n−1}\{0,1,\ldots,n-1\}, its residue (least non-negative residue).

Congruence is an equivalence relation: a≡aa\equiv a (reflexive); if a≡ba\equiv b then b≡ab\equiv a (symmetric); if a≡ba\equiv b and b≡cb\equiv c then a≡ca\equiv c (transitive).

On the number line, 22, 66 and 1010 are each 44 apart, so 2≡6≡10(mod4)2\equiv6\equiv10\pmod4.

0123456789101112132610

What is the least non-negative residue of −3-3 modulo 77?

Laws of congruences

You can add, subtract, multiply and take powers of congruences, reducing at each stage.

If a≡ba\equiv b and c≡d(modn)c\equiv d\pmod n, you can add, subtract, multiply and raise to powers. For repeated powers, find a power that is ≡1\equiv1.

Replace large numbers by small residues, including negative ones such as 10≡−1(mod11)10\equiv-1\pmod{11}, before multiplying. The power law is ak≡bka^k\equiv b^k for any positive integer kk.

  1. 1

    Reduce each number modulo n

    Use small or negative residues, for example 10 ≡ −1 (mod 11).

  2. 2

    Add, subtract, multiply or take powers

    Apply the same operation to the residues.

  3. 3

    Reduce again

    The result is congruent to the original calculation.

Using congruences
  • Additiona±c≡b±da\pm c\equiv b\pm d
  • Multiplicationac≡bdac\equiv bd
  • Powersak≡bka^k\equiv b^k

Worked example

Given a≡4a\equiv4 and b≡7(mod9)b\equiv7\pmod9, find a+ba+b, abab and a2−3ba^2-3b modulo 99. Then find 3102(mod11)3^{102}\pmod{11}.

If x≡5(mod8)x\equiv5\pmod8, what is x2(mod8)x^2\pmod8?

Tests for 2, 4, 5 and 10

Only the last digit matters for 22, 55 and 1010, and the last two digits for 44.

Because 10≡0(mod2)10\equiv0\pmod2, (mod5)\pmod5 and (mod10)\pmod{10}, only the last digit matters: divisible by 22 if it is even, by 55 if it is 00 or 55, by 1010 if it is 00.

Because 100≡0(mod4)100\equiv0\pmod4, a number is divisible by 44 if its last two digits form a multiple of 44.

Example: 372 416372\,416 ends in 1616, so it is divisible by 44. Testing only the last digit for 44 is a common slip.

  1. 1

    Last digit is 6

    Even, so divisible by 2. Not 0 or 5, so not by 5 or 10.

  2. 2

    Last two digits are 16

    16 is a multiple of 4, so 372 416 is divisible by 4.

Example: 372 416
  • 10≡0(mod2,5,10)10\equiv0\pmod{2,5,10}check the last digit
  • 100≡0(mod4)100\equiv0\pmod4check the last two digits

Is 5 7345\,734 divisible by 44?

Tests for 3, 9 and 6

A number is congruent to its digit sum modulo 33 and modulo 99.

Because 10≡1(mod3)10\equiv1\pmod3 and (mod9)\pmod9, a number is congruent to its digit sum modulo 3 and modulo 9.

So it is divisible by 33 if the digit sum is, and by 99 if the digit sum is a multiple of 99. A number is divisible by 66 if it is divisible by both 22 and 33.

To make a number divisible by 9 with one unknown digit, subtract the other digits' sum from the next multiple of 9.

  1. 1

    Add the digits

    3 + 7 + 2 + 4 + 1 + 6 = 23.

  2. 2

    Compare with 3 and 9

    23 is not a multiple of 3 or 9.

  3. 3

    Conclude

    So 372 416 is divisible by neither 3 nor 9, and therefore not by 6.

Example: 372 416
  • 10≡1(mod3 and 9)10\equiv1\pmod{3\text{ and }9}number ≡ digit sum

Worked example

Test 372 416372\,416 for divisibility by 33, 99 and 66.

Which digit dd makes 47d47d (a three-digit number) divisible by 99?

The test for 11

A number is divisible by 1111 when its alternating digit sum is a multiple of 1111.

Because 10≡−1(mod11)10\equiv-1\pmod{11}, a number is divisible by 1111 if its alternating sum of digits is a multiple of 1111 (including 00).

Alternate signs starting from the units digit. For 372 416372\,416: 6−1+4−2+7−3=116-1+4-2+7-3=11, so it is divisible by 1111. Using the plain digit sum is a common mistake.

For numbers with unknown digits, write each test as an equation or condition, solve each, then combine. Coprime divisors combine: a number divisible by 44, 99 and 1111 is divisible by 396396.

  1. 1

    Alternate signs from the units digit

    6 − 1 + 4 − 2 + 7 − 3.

  2. 2

    Evaluate

    = 11.

  3. 3

    Conclude

    11 is a multiple of 11, so 372 416 is divisible by 11.

Example: 372 416
  • 10≡−1(mod11)10\equiv-1\pmod{11}number ≡ alternating digit sum

Is 2 7282\,728 divisible by 1111?

Try an exam question

The three-digit number 6d46d4, where dd is a digit, is divisible by both 44 and 33. Find the possible values of dd.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find the least non-negative residue of a+ba+b modulo 99.

1 mark, marked against the mark scheme

Revision notes