Modular arithmetic and divisibility tests

Modular arithmetic and divisibility tests Flashcards

Spec 5.3 · Edexcel A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

12 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 12 cards
When is a≡b(modn)a\equiv b\pmod n?
When nn divides a−ba-b, equivalently aa and bb leave the same remainder on division by nn.
State the three properties of congruence.
Reflexive a≡aa\equiv a; symmetric (a≡b⇒b≡aa\equiv b\Rightarrow b\equiv a); transitive (a≡b, b≡c⇒a≡ca\equiv b,\,b\equiv c\Rightarrow a\equiv c).
Addition and subtraction law?
If a≡ba\equiv b and c≡dc\equiv d then a±c≡b±d(modn)a\pm c\equiv b\pm d\pmod n.
Multiplication law?
If a≡ba\equiv b and c≡dc\equiv d then ac≡bd(modn)ac\equiv bd\pmod n.
Power law?
If a≡b(modn)a\equiv b\pmod n then ak≡bk(modn)a^k\equiv b^k\pmod n for positive integers kk.
Divisibility test for 2, 5 and 10?
Last digit: even; 00 or 55; 00.
Divisibility test for 4?
The last two digits form a multiple of 4.
Divisibility test for 3 and 9?
The digit sum is a multiple of 3, or of 9.
Divisibility test for 6?
Divisible by both 2 and 3.
Divisibility test for 11?
The alternating digit sum (starting from the units digit) is a multiple of 11, including 0.
Why does the 9 test work?
10≡1(mod9)10\equiv1\pmod9, so each place value is congruent to 1.
Why does the 11 test work?
10≡−1(mod11)10\equiv-1\pmod{11}, so place values alternate between 11 and −1-1.

Flashcards