Modular Arithmetic Booklet
Modular Arithmetic Booklet
Arithmetic
f;2 8 Clock arithmetic and addition
Example 1 __ • 12
. •
. 11
If we count around a clockface, the sequence of numbers is 1, 2, 3, 4, °10
..., 12. The pattern is repeated after we get to 12. The set is finite. .9/
For example, if we start at 8 on a clockface and add 7, we finish at 3. .8
.7 6 5.
e
Example 2
•• Egg timers work in a similar way. Suppose the indicator on the dial is at
a
3 minutes. In a further 2 minutes it will be at 1. Thus in this system,
3+2=1.
Assuming this indicator keeps going around, in 5 more minutes it will
2
~
be at 2. That is, 1 + 5 = 2. .:
.I
3 2
17 lvuxiuiar arithmetic (optional) 4~~' ',"
Wed
430 Clock arithmetic and addition
10 Draw a pattern similar to the pattern in question 9 for a person who goes to the
gymnasium:
A every day B every third day
C every fourth day D every fifth day
For each pattern, answer the following questions.
(a) If the person trains on Monday, what time will elapse before training on Monday
again?
(b) How many lines are found in the pattern?
(c) How many times do you move around the clock before arriving back at the
starting point?
11 State the modulus of the following.
(a) the months of the year (b) a 3 minute egg timer
(c) the days of the week (d) an analogue clock
(e) a clock using the digits 0, 1, 2, 3, 4, 5 (f) a VCR
Residue
The residue of an integer n mod m is the remainder when n is divided by m.
All integers in mod 6 with the same remainder are said to be congruent in mod 6
arithmetic. For example,
19 == 37 (mod 6)
Congruence
The integers x and y are said to be congruent
mod m. In this case we write x =;: y (mod m).
mod m if they have the same residue JI
.
Notation
The set of residues in mod 5 arithmetic is {O,1, 2, 3, 4}. This set is often referred to
as 15.
Similarly, in mod 7 the residues are given by 17 = {O, 1, 2, ... , 6}.
Opposites exist in modular arithmetic also. For example, 3 + 2 == 0 (mod 5). Thus 3 is th
opposite of 2, and 2is the opposite of 3, in mod 5.
17 Modular arithmetic (optional) 4.d1
..-;~~&]
;
l
Subtraction is an operation where we add the opposite'.
I
It
i
f
I Examples
I
t,
t 1 3 - 4 = 3 + 1(mod.5) 2 1 - 5 = 1 + 2 (mod 7)
I
~ = 4 (mod 5) = 3 (mod 7)
l i.
t
I
~ The opposite of 5
~
is 2 in mod 7.
I
.\',
•.
,' Exercise 17C Opposites and subtraction
. 1 Write down the opposites of the following in mod 3.
, (a) 1 . (b) 2 (c) 0
t
~..
2 Write down the following
(a) -3
in
(b)-4
15'
(c) -1. (d) -2
~~~I~~L~~_I~~IL~~~
7 8 2 3 5 4 769 1
Example 1
J5 Consider the multiplication table in mod 5 Us).
Each entry belongs to Js. For example,
x 0 '11 2 3 4
3 x 4= 12= 2 (mod 5)
010
1 0
0
1
0
2
0
3
0
4
and =
4 x 2 = 8 3 (mod 5)
2 0 2 4 .1 3
3 0 3 1 4 2
4 0 4 3 2 1
Exe~~~lse17D Multiplication
1 Use the multiplication table in Js above to evaluate the following.
(a) (3 x 4) x 2 (b) 4 x 0 (c) 2 x 2 x 2
(d) (2 x 3) x 4 (e) 4 x 4 (f) 32
(g) 2 3 (h) 1 x 2 x 3 x 0 (i) 43
(j) (2 x 3) + (3 x 4) (k) 2 - (3 x 4) (1) 22 + 32
2 Make multiplication tables for mod 2, mod 4, mod 6, mod 7, mod 8, mod 9, mod 10 and
mod 12 arithmetics, and keep them for further reference.
3 Compute in mod 4.
(a) 2 x 3 (b) 2 x 3 x 2 (c) 22
(d) 3(1 + 2) (e) 3 x 2 + 1 x 2 (f) 32
(g) 3 x0 (h) 22 + 32 (i) 33
r
17 Modular arithmetic (o-ptional)
4 Simplify in h.
(a) 5 x2 (b) 3 x 2x4 (c) 52
Example 2
Evaluate (3 x 7)6 (mod 6).
Solution: ' .. (3 X 7)6 == 36 (mod 6)
== 3 (mod 6)
5 Study Example 2, then evaluate.
(a) (2 x 3)4 (mod 5) (b) (2 x 3)6 (mod 4) (c) 5 x 6 (mod 7)
(d) 7 x 8 (mod 10) (e) (4 x 5)8 (mod 10) (f) (3 x 7)10 (mod 10)
(g) 3+ 4 x 2 (mod 8) (h) 52 + 32 + 42 (mod 6) (i) 103 (mod 9)
(j) 104 (mod 12)
6 Evaluate X2 if:
(a) x = 2 (mod 5) (b) x = 3 (mod 5) (c) x= 7 (mod 8)
(d) x = 9 (mod 12) (e) x = 3 (mod 7) (f) x = 8 (mod 10)
7 Evaluate X2 + 3x + 2 if:
(a) x = 2 (mod 5) (b) x = 3 (mod
7) (c) x = 5 (mod 8) .
(d) x = 7 (mod 9) (e) x = 7 (mod 10) (f) x = 9 (mod 12)
'Examp'le 3·
-Evaluate 17 x 29 == a (mod 7), where a is in 17'
;}1pproach 1: 17 x 29 = 493 (mod 7)
T. == 3 (mod 7)
c. pproach 2: 17 x 29 = 3 x 1(mod 7)
. == 3 (mod 7)
8 Study Example 3, then evaluate the following where a is in 17'
,. (a) 9 x 11 == a (mod 7) (b) 13 x 15 == a (mod 7) (c) 28 x 16 == a (mod 7)
(d) 36 x 50 == a (mod 7) (e) 5 x 8 x 11 == a (mod 7) (f) 222 == a (mod 7)
, ' Simplify the following in mod 5.
< (a) 24 x 27 (b) 31 x 32 x 33 (c) 104 x 216
: (d) 16 4 (e) 101 x 203 (f) 610
ample 4
'il~ider this example in mod 5:
) x 1 = 1 (mod 5) and 4 x 4 = 1 (mod 5)
'; can conclude that the square root of 1 in
~,45 is either 1 or 4.
(a) By considering the multiplication table in mod 5, find the square root(s) of 4.
!}:l) Does every element of Is have a square root? If not, which ones do?
',,"
'$6 Multiplication in modular arithmetic
11 Consider J7'
(a) Indicate which numbers have a square root or roots, and write them down.
(b) Which numbers do not have a square root?
12 Investigate square roots in J3, J4 and J9. Write down your conclusions.
ChaUengingproblem Remainders
(a) Find the remainder when 74 is divided by 100.
(b) Hence or otherwise, find the remainder when 71999
is divided by 100.
J5
If we look at the multiplication table for mod 5 arithmetic,
we observe that:
2x3=1
4x4=1
1x 1= 1
3x2=1
pIes
" 3 = 4 x 2 (mod 5)
== 3 (mod 5)
4 = 1 x 2 (mod 7)
== 2 (mod 7)
R
.. "- ~'.~
-"-." \ .. '-. '" ~
Solving equations
The normal rules apply when solving equations in modular arithmetic.
Examples
13x=4 (mod 5)
x=4+3 (mod 5) Divide both sides by 3.
=4x2 (mod 5)
=3 (mod 5)
17 Modular arithmetic (optional) . 4a~;fl~i/jj~:
H: 4x - 5 = 7 S: x + x = 1
c
A: :5 =4
.. I: 3 - c = 10 B: 9y= 7
. G: 2x +5 =3 N: 5d=7
2 4 10 3 6
~,AO Solving equations
,
.j
(
The following words have been used in this chapter. They have (
been written without their vowels. Can you complete the words?
Shopping Centre, and this is not representative of the general population, 4 (a) 13 em (b) 45° 596 mm 'I
t I. it!: ::9;, ;;J .' :.?: ;)~3\ ,;~ir.6;:,:7.8
i
6 (a) , ., (b) AB = 4 units, BC = 3 units (e) 5 units r £P} 0 1 2 3 415 6 7 8
;J\ 1 2 3 4 5 ·6 P 8 I 0
t;C. 2 3· 4 5 I 6 7 8 0 1
I! 3:' 3 4 5 6 I 7 8 0 1 I 2
•Ii '.4'> 4 5 6 7 8' o 11 2 3
.5': 5 . 6 7 8. 0 1 I 2" 3 4
ft'I. }6\ 6 7 1 8 0 1 2 3 4 5
{;:I;: 7 8 0' 1 2 3 4 516
~ '8" 8 0 1 2 I 3 4 5 6 7.
(e) mod 10 (f) mod 11
",\:;, ;0/,' ••:1.·····.I.~.2'i1!3,.1\4.;"li;hj(; ~.:;,9: •.119.
I ~:i!J:; 0
~t1:11
1. 2.- 3. 4
3. '4 ,5
5 6 7 8 9 :Qf 0
',';1.', 1
1 2 3 4 5 6
'.T"
7
.
8 9 110.
~ 1 2 6 7 8 9 0 21 3: 4 5 I 6 7 8 9 10 I 0
(e) Car model sa! s (al n+17=44 (b) ll-n=-3 ~ ~:?:l.' 2, 3 4. 5 6 7 8 9 0 1 /2,. 2 3 4 5 I6 .10
7 8 9 o I 1
n=27 n=14 i ;~~f~3 4 5. 6 7 .8 9 0 ,1 2 '3,: 415
3 6 7. 819 10 0. 11 ?
.<J
6
~"r If1 '
9 (a) LA = LD, LB = LE, LBCA = LECD (b) Equiangular
(e) AB and DE, AC and DC, BC and EC I :~~:~:
415 6 7 8 9 0 1 . 2 3 (;;4 4
s: 5 6 7
5 i 6 7 8 9 10. 0 1 213
!
5
:- t(IHl 5
:;,: ,:.
I 6 7" 8 9 0 .1 213 4 8 9 10 0 1 2 3 4
<=: 10 -7 11 (a) 19000 mm x 20000 mm (b) Studeht's drawing
'"~ 0. 1 I5
4
t~;:i 1 12 (a) In ss JOM and LOK, f~62 .'~' 7 8 9. 0 1 2 3 .4 5 ','6" 6 7 8 9 110 2 3 4
I,
o I:·".
S 3
I LMJO = LKLO (equal alternate Ls) ~t'i;7' .8 9 I0 .1 . 2 3 4 516 ·.·.·7 7 '8 9 10 0 1 .2 3 415 I 6
((, 1/ If;" LJMO = LLKO (equal alternate Ls) i;Ii;J '8 9 o .1 .2 3 4: 5 6 7. ~8 8 9 10 0 1 2 3 I 4 5 6 7
~'" 2
y
I
'"
00' i> I;; JM = LK (opposite sides of parallelogram)' :;9;., 91 0 1 2 ·3 4 5, 6 1'18 :9", 9 10 ·0 L1. 2 3 4 5 I 6 I 7 Is
I
1 I-- r- .'. !!.JOMes ilLOK (AAS)
I,':" I:",' 10 10 0 1 2 I 3 ·4 5 6 I 7 8 I 9
o ., JO = LO and MO = KO (corresponding sides)
A B C Thenew (b) The diagonals of a parallelogram bisect each other. 5 (a)1 (b) 3 (e) 1 (d) 0 (e) 6 (f) 5 (g) 0 (h) 8 (i) 5 6 (al l (b) 0 (e) 3 (d) 0 (el I (f) 4
p
Wallaby 7 (a)2 (b) 0 (e) 1 (d) S (e) S (f) 3 S (a) 3 (b) 7 (c) Saturday (d) Friday (e) Saturday
Model
9 (a) 2 weeks (b) 7 lines (c) 2 times
~xeH§se 'i!P'~ 10. . Sun Sun (a) A 7 days, B 3 weeks,
C 4 weeks, D S weeks
1 modS 2000 M1 001 001 ~1 WI ~3 WI W3
Sat £,/' ~Mon Sat / 1\ "<, Mon (b) All 7 lines (e) A 1 time,
(i) 3 (k) 3 (l) 3
B 3 times, C 4 times, D 5 times
~ mod 3 (a) 0 (b) 1 (e) 2 (d)2 11 (a) niod 12 (b) mod 3
.4 (e) 0 (f) 0 (g) 0
o lit$'l i;fi)"i;tmlft :j':21, (c) mod 7 (d) mod 12
I~;:o~:\0 I 1 2 (e) mod 6 (f) mod 24
Tue Fri
'2 Wf'! 1 'I 2 0
3, ~2tl 2f 0 11
4, (a) mod 6 (b) mod 7
•~ ~.
Thu' Wed
1
.1.
'5
5
~
0
~:
'~.
;i1if~fa<ffi;tfi4~tit{51;~lit~
31 .4 I 5,16
4 151 6 I 0
l
R,
~.o:
Sun' Sun
~;: .
1
~ -. ,
:~.
IllKelll'\l:lise ~ 71=
..
' ~ 1(a) x = 3 (b) x = 4 (c) x·= 1 (d) x = a (e) a = 2 (f) Y = 1 (g) c = 2 (h) x = 2 2 (a) a = 3 (b) c = 5 (c) a =4
~·::/i· (d) y = 2 (e) c = 5 (f) Y = 2 (g) x = 5 (h) x = t6 3 (a) x = 4 (mod 6) (b) a = 5 (mod 9) (c) d = 2 (mod 7)
(d) c '" 2 (mod 6) (e) a = 2 (mod 5) (f) x = 2 (mod 7) (g) x = 9 (mod 11) (h) x = 6 (mod 7) (i) x = 4 (mod 5)
a
(i) x = (mod 5) (k) a = 1 (mod 5) (I) x = 2 (mod 7)
Riddle What do you have if you... BIG HANDS
Challenging problem Congruent square
(2n)" = 4n' '" 0 (mod 4)
(2n + 1)" = 41i' + 4n + 1 = 4(11'+ n) + 1 '" 1 (mod 4)
Since all integers may be written in the form 211or 2n + 1, the square of any integer is congruent to either 0 or 1 in !•.
Literacy activity Missing vowels M0DULUS ARITHMETIC RESIPUE CONGRUENT INTEGER
MULTIPLICATION EQUATION OPPOSITE INVERSE RECIPROCAL DMSION REMAINDER
.~
~.
---- . ...-.-.---.,---.--~
- ---~ ~-=-
B.~.t4 Answers
W'"
Ixerr@mse 'I 7~
1 (a) 0, 1, 2, 3, 4 (b) 0, 1, 2, 3, 4, 5, 6 2 (a) 1 (b) a (c) 2 (d) a (e) 1 (f) 3 (g) 4 (h) 1 (i) 4 (j) 2
3 (a) 6 (b) a (c) 4 (d) 3 (e) 2 (f) 2 (g) 5 (h) a (i) 4 (j) 4 4 (a) 1 (b) a (c) 2 (d)6
5 (a) 8, 15, 22, 29 (b) 8, 13, 18, 23 (c) 10, 16, 22, 28 6 (a) T (b) T (c) T (d) F (e) F (f) F
7 (a) 2 (b) 6 (c) 3 (d) 2 (e) 3 (f) 2 8 (a) {O,1, 2) (b) {a, 1, 2, 3) (c) {a, 1, 2, 3, 4, 5, 6, 7,8)
9 (a) 46 == 1 (mod 5) (b) 83 == 3 (mod 5) (c) 109 == 4 (mod 5) (d) 153 == 3 (mod 5) (e) 550 == 0 (mod 5)
10 (a) 5 (b) 2 (c) 2 .(d) 5 (e) 3 (f) 7 . 11 (a) 4 (mod 5) (b) 4 (mod 7) (c) 4 (mod 7) (d) 3 (mod 6)
(e) a (mod 3) (f) 1 (mod 4)
Riddle When visitors knock... VITAMIN
Challenging problem Operation 0 (a) (i) 5 (ii) 4 (iii) -10 (b) No
ix:errciise 17(;
1 (a)2 (b) 1 (c) 0 2 (a) 2 (b) 1 (c) 4 (d) 3 3 (a) 2 (b) 5 (c) 1 (d) 6 (e) 7 (f) 7 (g) 5 (h) a
4 (a) 6 (mod 7) (b) 3 (mod 5) (c) 3 (mod 5) (d) 7 (mod 10) (e) 8 (mod 10) (f) 4 (mod 5) (g) 2 (mod 4)
(h) a (mod 6) (i) 3 (mod 5) (j) 10 (mod 11) 5 (a) 2 (b) 2 (c) 0 (d) 3 (e) 2 (f) 0 6 (a) mod 4 (b) mod 7
(c) mod 10 (d) mod 7 (e) mod 8 (f) mod 3
Riddle Who gets the sack... THE POSTMAN
Exercmse 17.D
1 (a) 4 (b) 0 (c) 3 (d) 4 (e) 1 (f) 4 (g) 3 (h) 0 (i) 4 (j) 3 (k) a (1) 3
2 mod 2 mod 4 mod 6 .
mod 7 mod 8
New Course Mathematics Year 8 ' 5Q\~
mod 12
3 4 5 11
68 10 10
~o' 3 " 9
o . 4 88'
3 8~,/1 7
:lo',
9 8 761
3 (a) 2 (b) 0 (c)O (d) 1 (e) 0
(f) 1 (g) 0 (h) 1 (i) 3 4 (a) 4 (b) 0 (c) 1 (d) 2 (e) 5 (f) 4 (g) 4
(h) 3 1 (j) 1 (k) 0 (1)4, (m) 1 (n) 2 (0) 4 5 (a) 1 (mod 5) (b) 0 (mod 4) (c) 2 (mod 7) (d) 6 (mod 10)
(i)
(e) a (mod 10) (f) 1 (mod 10) (g) 3 (mod 8) (h) 2 (mod 6) (i) 1 (mod 9) (j) 4 (mod 12) 6 (a) 4 (mod 5)
(b) 4 (mod 5) (c) 1 (mod 8) (d) 9 (mod 12) (e) 2 (mod 7) (f) 4 (mod 10) 7 (a) 2 (mod 5) (b) 6 (mod 7)
(c) 2 (mod 8) (d) a (mod 9) (e) 2 (mod 10) (f) 2 (mod 12) 8 (a) t (b) 6 (c) 0 (d) 1 (e) 6 (f) 1 9 (a) 3
(b) 1 (c) 4 (d) 1 (e) 3 (f) 1 10 (a) 2 or 3 (b) No. a, I, 4 do. 11 (a) 0, I, 2, 4 (b) 3, 5, 6
12 J3 and J4: a, 1 have square rootts).
J9: a, 1,4,7 have square root(s).
Challenging problem Remainders (a) 1 (b) 43
Riddle How can you build ... USE QUICKSAND
Challenging problem Is it true? (a) No (b) When m is a prime'
ltxell'cise 117F
1 (a) x = 3 (b) x = 4 (c) x = 1 (d) x = 0 (e) a = 2 (f) Y = 1 (g) c =2 (h) x =2 2 (a) a =3 (b) c =5 (c) a =4
(d) y = 2 (e) c = 5 (f) Y = 2 (g) x = 5 (h) x = 1~6 3 (a) x = 4 (mod 6) (b) a = 5 (mod 9) (c) d = 2 (mod 7)
(d) c == 2 (mod 6) (e) a = 2 (mod 5) (f) x = 2 (mod 7) (g) x = 9 (mod 11) (h) x = 6 (mod 7) (i) x = 4 (mod 5)
(j) x = 0 (mod 5) (k) a = 1 (mod 5) (1) x = 2 (mod 7)
Riddle What do you have if you... BIG HANDS
Challenging problem Congruent square
(2n)2 = 4112== a (mod 4)
(211+ 1)2 = 41i2 + 411+ 1 = 4(n2 + n) + 1 == 1 (mod 4)
Since all integers may be written in the form 211or 211+ 1, the square of any integer is congruent to either a or 1 in J4'
Literacy activity Missing vowels MODULUS ARITHMETIC RESIDUE CONGRUENT INTEGER
MULTIPLICATION EQUATION OPPOSITE INVERSE RECIPROCAL DIVISION REMAINDER
_, _, .= ,_:--,.
;'.~~' '~__' __._ _ ._..::c?
I
.- (';..2 Answers
[l~'~~=~t,~,-.C~i~I~I=]
I,!,
! !
I,,!
. I I
I
;;
i': i 3
!,
J:
! ii',
I - ,I
!
!
!
'
I
I
tr
~
,
!
i
-2
A
~--~l-j=l---I
II I I B; i
ti-
~--+-1---~-+-1--+-~
I! !!! I !
ll:;
p
! "';1 2 3 4
itp
f--1=1 --L-+--t---r-'-'~--I
i I I
~~_.w__ ...J._._._ ..". _ ... __;:..,__ 1 I
.!._._ ......• I ~ !
__ .....l.._,_.-i.-. __ J
7 (a) The width of the column for 'The new Wallaby' is twice that of the others. Also, the divisions on the vertical
scale are not equal, and it starts on 2000cars instead of on zero. (b) A 6000 cars, B 5000 cars, C 4000 cars, Wallaby
6000 cars
(c) Car model sales 8 (a) n + 17 = 44 (b) 11 - n = -3
n =27 n = 14
6 9 (a) LA = LD, LB = LE, LBCA = LECD (b) Equiangular
----
00
-ci
(c) ABand DE, AC and DC, BC and EC
5
§ 10 -7 11 (a) 19000 mm x 20000 mm ,(b) Studeht'sdrawing
00
::J 4 12 (a) In ils JOM and LOK,
0
,..!:;
.:t!.- 3 LMJO = LKLO (equal alternate Ls)
a: LJMO = LLKO (equal alternate Ls)
Q)
Cd 2
CIl
JM = LK (opposite sides of parallelogram)'
1 :. NOM = ilLOK (AAS)
0 .. JO = LO and MO = KO (corresponding sides)
A B C The new (b) The diagonals of a parallelogram bisect each other.
Wallaby
Model
1 mod 5 2 (a) 0 (b) 1 (c) 1 (d) 1 (e) 1 (f) 1 (g) 3 (h) 1 (i) 3
(j) 3 (k) 3 (1)3
3 mod 3 (a) 0 (b) 1 (c) 2 (d)2
(e) 0 (f) 0 (g) 0
2. 3 45 s -r. T
(e) mod 10
5 (a) 1 (b) 3 (c) 1 (d) 0 (e) 6 (f) 5 (g) 0 (h) 8 (i) 5 6 (a) 1 (b) 0 (c) 3 (d) a (e) 1 (f) 4
7 (a) 2 (b) 0 (c) 1 (d) 5 (e) 5 (f) 3 8 (a) 3 (b) 7 (c) Saturday (d) Friday (e) Saturday
9 (a) 2 weeks (b) 7 lines (c) 2 times
Thu~:::::::=:::::::::"~Wed
Sun Sun
~>
~;.
~-.
1;.1.,-.. -'
Ji:. ./'