16
An Introduction to Modular Arithmetic and its Applications By Leslie Leung Modular arithmetic can be defined as a system of arithmetic for integers. 4 It is a mathematical tool that is widely used in daily life as well as solving mathematical problems.
Explanation of notation: a ؠ b ሺmod nሻ
ሺread as ′
a is congruent to b modulo n ′ ሻ
ܽ and
ܾ is a multiple of
݊ , or in other
It means that the difference between
ܽ and
ܾ give the same remainder when divided by ݊ .
words, when both
The most common use of modular arithmetic is perhaps the 12-hour clock. A day has 24 hours but a cycle of the clock lasts only 12 hours. Therefore, when the 21 ؠ 9 ሺmod 12ሻ . ࡿ࢚ࢇ࢚࢘ࢋ࢘ ࡽ࢛ࢋ࢙࢚: ࢃࢎࢇ࢚ ࢚ࢋ ࢊࢋ࢙ ࢚ࢎࢋ ࢎ࢛࢘ ࢉࢉ ࢙ࢎ࢝ ࢎ࢛࢙࢘ ࢇࢌ࢚ࢋ࢘ ? Answer: 100 ؠ 4 ሺmod 12ሻ , so the clock shows 4 o'clock. Before moving on to explore how modular arithmetic can be used to solve other problems, a few 'laws of modular arithmetic' has to be explained. 1) Addition/Subtraction time is 21:00, the clock shows 9 o'clock because
If a ؠ c ሺmod nሻ, b ؠ d ሺmod nሻ , then ሺa െ bሻ ؠ ሺc െ dሻ ሺmod nሻ 2) Multiplication Also,
ሺa bሻ ؠ ሺc dሻ ሺmod nሻ
If a ؠ c ሺmod nሻ, b ؠ d ሺmod nሻ, then ab ؠ cd ሺmod nሻ Proof:
c ൌ a pn, d ൌ b qn , where
p is an integer. cd ൌ ሺa pnሻሺb qnሻ ൌ ܉܊ aqn bpn pqn ଶ
Let
4 http://en.wikipedia.org/wiki/Modular_arithmetic
Made with FlippingBook - Online Brochure Maker