Remainder or modular Arithmetic
There are many rules for recognizing when whole numbers are multiples of 2,
3, 4, 5, 6, 7, 8, 9,10 and 11. Those rules are consequences of modulo or
remainder arithmetic. Introduction of the phrase remainder arithmetic
may be a site invention or not, but the phrase points to the use we will make of
modular arithmetic.
Long division implies for any pair of natural numbers d > 0 and n >
0, there are naturals numbers q > 0 and r such that
0 < r < d and
n = qd +r
Here the quotient q = the number of whole times that the divisor
d goes into the dividend n, and r = the remainder.
Two natural numbers n and m are said to be equivalent or equal
modulo d, when there remainders on division by d are equal. In this case, we
write
n = m, modulo d.
Equality modulo a whole number or divisor d is
-
reflexive, that is, each number n = itself,
modulo d, or equivalent n = n, modulo d, for each natural number n.
-
symmetric, that is, n = m modulo d
when and only when m = n modulo d, and
-
transitive, that is, if n = m
modulo d, and m = t modulo d then n = t modulo d.
A whole number n is divisible by the divisor d when and
only when n = qd for some whole number q. That is when and only when
n = 0, modulo d and when and only when n is a whole or natural number
multiple of the divisor d. The number 0 is a multiple of all divisors d.
Observe, if n > m then n = m, modulo d when and only
when n - m is a multiple of d while if n < m then n =
m, modulo d when and only when m -n is a multiple of d.
Remainder Calculations are based on the following properties or
theorems.
Theorem: Suppose m, n, u and v are natural
numbers. Suppose d > 0 is a whole number. If m = n,
modolo d and u = v, modulo d then (i) m + u = n +v
modulo d, and (ii) mu= nv, modulo d.
Proof: First, m = n, modulo d,
implies m = a d +r and n = b d +r for some whole numbers a, b and a
common remainder r with 0 < r < d. Likewise, u = v, modulo
d, implies u = A d + s and v = B d +s for some natural numbers A,
B and a common remainder r with 0 < s < d.
Arguments for (i): Suppose (m+ u) > (n+v)
then
(m+ u) - (n+v)
= (ad +r + Ad+s) - (bd+r + Bd+s)
= (a+A)d + (r+s) - [(b+B)d + (r+s)]
= (a+A)d-(b+B)d
= [(a+A)-(b+b)]d
is a multiple of d, and hence (i) m + u = n +v
modulo d holds when (m+ u) > (n+v). The case where (n+v) >
(m+u) follows similarly.
Arguments for (ii): Suppose m u > nv
then
mu - nv
= (ad +r)(Ad+s) - (bd+r)(Bd+s)
= aAd2 + asd+ Ard+ rs - [bBd2 + bsd+ Brd+ rs]
= [{(aA)-(bB)}d + (as-bs)]d
is a multiple of d, and hence (i) m u = n v
modulo d holds when m u > nv. The case where nv > mu
follows similarly.
Remainder Calculations for Negative Numbers
Observe if m > 0 is a whole number with m = r, modulo
d, then - m = -r = n-r, modulo d,
For example 18 = 3 modulo 5. Therefore,
modulo 5: -18 = - 3 = 0 - 3 = 5 -3 = 2.
Observe 18 = 3 x 5 + 3 while -18 = - 20 + 2 = (-4)x5 +
2.
Calculator Usage: For every divisor d > 0 and every
number N, there is a unique integer q such that qd < N <
(q+1)d so that r = N-qd satisfies 0 < r < d. With the aid
of a calculator, if N is positive, the whole number part of the decimal
representation of the computed value of N/d gives q > 0. But if N is
negative, the whole number part of the decimal representation of the computed
value of N/d gives q+1 < 0, and q is one less than the whole
number part of N/d.
Recognizing Whole Number Multiples of 2, 3, 5, 9 & 11 via
their Decimals Form
As a student, you need to be proficient and quick with exact
arithmetic with whole numbers less than 100 and their ratios. Some of
the remainder calculation and divisibility rules below can be used quickly.
The rest are curiosities.
Decimal Based Rules for remainders for whole numbers, modulo 2,
3, 5, 9 & 11, follow.
-
Remainder on division by 2 is 0 if last digit is even, that
is, a 0, 2, 4, 6 or 8.
-
Remainder on division by 2 is 1 if last digit is odd, that
is, a 1, 3, 5, 7 or 9.
-
Remainder on division by 5 is 0 if last digit is 0 or
5.
-
Remainder on division by 5 is 1 if last digit is 1 or
6.
-
Remainder on division by 5 is 2 if last digit is 2 or
7.
-
Remainder on division by 5 is 3 if last digit is 3 or
8.
-
Remainder on division by 5 is 4 if last digit is 4 or
9.
-
Remainder on division by 10 is given by the last digit.
-
Remainder on division by 100 is given by the last two digit.
-
Remainder on division by 1000 is given by the last two
digit.
-
Remainder on division by 3 is given by the sum of digits,
modulo 3, as 10k = 1, modulo 3, for all natural numbers k..
-
Remainder on division by 9 is given by the sum of digits,
modulo 9,as 10k = 1, modulo 9, for all natural numbers k..
-
Remainder on division by 11 is given by the alternating sum
of digits, modulo 11, ,as 10k = (-1)k, modulo 11, for
all natural numbers k.. Knowledge of remainder arithmetic for integers
required here.
Reasons to explain the above rules and further ones
follow.
Remainders Modulo 2
Observe 10k = 5k2k
= 0, modulo 2, for all whole numbers k > 0. Therefore
-
243 = 2 x 102+ 4 x 10 + 3 = 0 + 0 + 3
= 3 = 3 =1, modulo 2.
-
6825 = 6 x 103 + 8 x 102+ 2 x 10 + 5 =
0 + 5 = 1, modulo 2.
-
52300 = 5230 x 10 = 0, modulo 2
In general, the remainder, modulo 10, of a n-digit decimal
whole number equals the remainder modulo 2 of the last digit. For
example,
479 = 47 x 10 + 9 = 0+ 9 = 1, modulo 2
Remainders, Modulo 3
Now we calculate a few remainders modulo 3. For that, observe
10 =1 , modulo 3
100 = 102 = 12 = 1, modulo 3.
1000 = 103 = 13 = 1, modulo 3.
Repeated calculations (mathematical induction) implies
10k = 1, modulo 3. for all
natural numbers k.
Again, do the calculations for k = 0, 1, 2, 3, 4 and 5, or apply
mathematical induction.
Therefore with equalities modulo 3
243 = 2 x 102+ 4 x 10 + 3 = 2*1+
4*1 + 3 = 2+ 4 + 0 = 6 = 0, modulo 3.
Therefore with equalities modulo 3,
modulo 3: 6821 = 6 x 103 + 8 x 102+
2 x 10 + 1 = 6 + 8 + 2 + 1 = 0+ 8 + 3 = 8 = 2
The foregoing implies 6819 = 6821 -2 = 0 modulo 3.
Note: Putting modulo 3 before the
sequence of equalities provides an immediate context for them while putting
them after delays the justification. We may use both. Putting them before may
be site re-invention.
Computational short cuts may be possible.
For instance, remainder on division by 3 is
given by the sum of digits, modulo 3, as 10k = 1, modulo 3, for all
natural numbers k.. But in the sum of those digits, we may replace 0, 3, 6 and
9 by zero, 2, 5 and 8 by 2 and 1, 4 and 7 by 1.
Remainders, Modulo 4
The remainder, modulo 4, of a n-digit decimal whole number
equals the remainder modulo 4 of the last 2 digits. For example
6821 = 68 x 102+ 21 = 68*0 + 21 = 0 + 5 x 4 + 1 = 1
modulo 4.
Remainders Modulo 5
Observe 10k = 5k2k
= 0, modulo 5, for all whole numbers k > 0. Therefore
-
243 = 2 x 102+ 4 x 10 + 3 = 0 + 0 + 3
= 3 = 3 modulo 5.
-
6821 = 6 x 103 + 8 x 102+ 2 x 10 + 8 =
0 + 3 = 3, modulo 5.
-
475 = 47 x 10 + 5 = 0, modulo 5
-
52300 = 5230 x 10 = 0, modulo 5
In general, the remainder, modulo 5, of a n-digit decimal
whole number equals the remainder modulo 5 of the last digit. For
example,
479 = 47 x 10 + 9 = 0+ 9 = 1, modulo 5
Remainders Modulo 6
A curiosity
The remainder modulo 6 of a n digit whole number N is 0 if N is
a multiple of both 2 and 3. The decimal representation of N implies N =
q10 + r. Then q = a3+b where b is 0, 1 or 2. Therefore
modulo 6, N = q10 + r = (a3+b)10 + r = 30a + b 10 +r =
b10 +r,.
where b is 0, 1 or 2 and r is a single digit number 0 to
9.
Example 1: For the number 6835, we have
modulo 3, 683 = 6 + 8 + 3 = 8 = 2
Therefore b = 2, and
modulo 6, 6825 = 682*10 + 5 = 2*10+ 5 = 25 = 1.
Example 2: For the number 23558 we have
modulo 3, 23455 = 2 + 3 + 5 + 5 = 15 = 0
Hence with b = 0, we have
modulo 6, 23558 = 2355 x 10 + 7 = 0+ 7 = 2
Remainders, Modulo 7
A curiosity
The first 7 multiples of 7 are 7, 14, 21, 28, 35, 42 and
49. Therefore 50 = 1 modulo 7 and 100 = 2 modulo 7. We may use the
foregoing to a form and simplify a sequence of equalities, modulo 7, to compute
the remainder after division by 7.
For a first example
modulo 7: 34569 = 345x100 + 50 + 19
= 345x2 + 1+ 5
= 696
= 6 x
100 +50 + 46
= 6 x 2+ 1 + 4
= 17
= 3
Therefore 34569 = 3, modulo 7.
For a second example,
modulo 7: 654321 = 6543 x 100 + 21
= 6543 x 2 + 0
=
13086
= 130 x 100 + 50 + 36
= 260+ 1 + 1
= 262
= 2 x 100 +50 + 12
= 4 + 1
+ 5
= 10
= 3.
Therefore 654321 = 3, modulo 7.
Remainders, Modulo 8
The remainder, modulo 8, of a n-digit decimal whole number
equals the remainder modulo 8 of the last 3 digits. For example
76827 = 76 x 103 + 827 = 6 *0 + 827 = 0 + 206 x 4 +
3 = 3 modulo 4.
Remainders, Modulo 9
Now we calculate a few remainders modulo 9. For that, observe
10 =1 , modulo 9
100 = 102 = 12 = 1, modulo 9.
1000 = 103 = 13 = 1, modulo 9.
Repeated calculations (mathematical induction) implies
10k = 1, modulo 9. for all
natural numbers k.
Do the calculations for k = 0, 1, 2, 3, 4 and 5, or apply
mathematical induction.
Therefore with equalities modulo 9
243 = 2 x 102+ 4 x 10 + 3 = 2*1+
4*1 + 3 = 2+ 4 + 3 = 9 = 0, modulo 9.
Therefore with equalities modulo 9,
modulo 9, 6821 = 6 x 103 + 8 x 102+ 2 x
10 + 1 = 6 + 8 + 2 + 1 = 17 = 10 + 7 = 1+ 7 = 8
The forgoing implies modulo 9, 6822 = 6821 + 1 = 8+ 1 = 0.
Computational short cuts may be possible.
For instance, Remainder on division by 9 is
given by the sum of digits, modulo 3, as 10k = 1, modulo 3, for all
natural numbers k.. But in the sum of those digits, we may replace 9 by
zero
If you are a student, use only those shortcuts sanctioned by or
understandable to your teachers.
Remainders, Modulo 10
The remainder, modulo 10, of a n-digit decimal whole number
equals the remainder modulo 8 of the last digit. For example
76827 = 7682 x 10 + 7 = 7682 *0 + 7 = 7, modulo
10.
Remainders, Modulo 11
Now we calculate a few remainders modulo 11. For that, observe
10 = -1 , modulo 11
100 = 102 = (-1)2 = 1, modulo 11.
1000 = 103 = (-1)3 = 1, modulo 11.
Repeated calculations (mathematical induction) implies
10k = (-1)k, modulo 9.
for all natural numbers k.
Do the calculations for k = 0, 1, 2, 3, 4 and 5, or apply
mathematical induction.
Therefore
modulo 11: 243 = 2 x 102+
4 x 10 + 3 = -2+ 4 - 3 = -1 = 10
modulo 11, 6821 = 6 x 103 + 8 x 102+ 2 x
10 + 1 = -6 + 8 - 2 + 1 = 1
Note 10k = (-1)k ,modulo 11,
implies the ones column (k=0) makes a positive contribution, the tens column
(k=1) makes a negative contribution, and the sign of the columns
alternates. So instead of writing
modulo 11: 6821 = -6 + 8 - 2 + 1 = 1
starting from the left, we can may write the alternating
sum
modulo 11: 6821 = 1 - 2 + 8 - 6 = 1
starting at the right with the one's digit.
That brings us to the last example for remainders, modulo 11 in
which we start the alternating sum with the one's or unit digit.
Modulo 11: 76823 = 3 - 2 + 8 - 6 + 7 = 10
Remainder Calculations for Negative Numbers
Observe if m > 0 is a whole number with m = r, modulo
d, then - m = -r = n-r, modulo d,
For example 18 = 3 modulo 5. Therefore,
modulo 5: -18 = - 3 = 0 - 3 = 5 -3 = 2.
Observe 18 = 3 x 5 + 3 while -18 = - 20 + 2 = (-4)x5 +
2.
Remark: For every divisor d > 0 and every number N,
there is a unique integer q such that qd < N < (q+1)d so
that r = N-qd satisfies 0 < r < d. With the aid of a
calculator, if N is positive, the whole number part of the decimal
representation of the computed value of N/d gives q > 0. But if N is
negative, the whole number part of the decimal representation of the computed
value of N/d gives q+1 < 0, and q is one less than the whole
number part of N/d.
|