Scribd
Upload
6 views17 pages

Modular Arithmetic

The document explains modular arithmetic, focusing on the concept of divisibility and congruence. It defines the notation for divisibility and congruence modulo n, providing examples and exercises for practice. Additionally, it discusses applications of modular arithmetic in real-world scenarios, such as clock arithmetic and finding remainders.

Uploaded by

rolloquefiona
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views17 pages

Modular Arithmetic

The document explains modular arithmetic, focusing on the concept of divisibility and congruence. It defines the notation for divisibility and congruence modulo n, providing examples and exercises for practice. Additionally, it discusses applications of modular arithmetic in real-world scenarios, such as clock arithmetic and finding remainders.

Uploaded by

rolloquefiona
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

MODULAR

ARITHMETIC
Notation

Consider integers 𝑎, 𝑏, and 𝑏 ≥ 𝑎 > 0.


The expression 𝒂|𝐛
is read as
“𝒂 divides 𝒃”

It could also mean that


𝑎 is a factor of 𝑏
𝑏 is divisible by 𝑎
𝑏 is a multiple of 𝑎
Which is correct?
𝟑|𝟔
or
𝟔|𝟑
𝟑 | 𝟔 is correct!
𝟔 | 𝟑 is false.
Hence, we write
𝟔 ∤𝟑
read as “6 does not divide 3”
𝟑|𝟔
3 is a factor of 6
6 is divisible by 3
6 is a multiple of 3
EXAMPLE

Write | or ∤ in the space


between the given to make the
statement correct.

1. 8 ___ 24
2. 7 ___ 27
3. 15 ___ −45
CLOCK ARITHMETIC

What can you say


about 1:00 P.M. and
1300H on the clock?
MODULAR ARITHMETIC
Definition:
• Modulo 𝒏
• Two integers 𝑎 and 𝑏 are said to be
congruent modulo 𝒏, where 𝑛 is a natural
𝒂−𝒃
number, if is an integer.
𝒏
• In this case, we write 𝒂 ≡ 𝒃 𝐦𝐨𝐝 𝒏 (also called
a congruence.)
• The number 𝑛 is called the modulus.
The same method can be applied to
12-hour-clock arithmetic.

Situations that repeat in cycles are


represented mathematically by using
modular arithmetic, or arithmetic modulo n.
𝒂 ≡ 𝒃 𝐦𝐨𝐝 𝒏
• 𝑎 and 𝑏 have the same remainder
when they are divided by 𝑛
• 𝑎 = 𝑘𝑛 + 𝑏
• 𝒏|𝒂 − 𝒃 where 𝑎, 𝑏, & 𝑛 ∈ ℤ; 𝑛 > 1
𝑎−𝑏
• = 𝑘, 𝑘 ∈ ℤ
𝑛

• 𝑎 − 𝑏 = 𝑘𝑛 (𝑎 − 𝑏 is a multiple of 𝑛)
The definition of congruence
also applies to negative values.

2 ≡ −3 mod 5
−8 ≡ 7 mod 5
−3 ≡ −8 mod 5
EXAMPLE

Determine whether the


congruence is true.

1. 29 ≡ 8 mod 3
2. 15 ≡ 4 mod 6
3. 7 ≡ 12 mod 5
4. 15 ≡ 1 mod 8
MORE!!!

Write ≡ or ≢ in the space


between the given to make the
statement correct.

1. 25 ___ 28 mod 3
2. 25 ___ 15 mod 8
3. 47 ___ 27 mod 9
APPLY!!!
Use modular arithmetic to answer the following items.
1. Find all possible values of 𝑛 if 11 ≡ 5 𝑚𝑜𝑑 𝑛
2. Solve 𝑥 + 3 ≡ 0 mod 7
2

3. Solve 𝑥 ≡ 2 mod 4
2

4. Solve 3𝑥 ≡ 1 mod 5
5. Find the ones digit of 2 2021
.
APPLY!!!
6. 9 is divided by 4. What is the remainder?
3

7. Find the remainder when 2 130


is divided by 7.
8. Find the remainder when 3 400
is divided by 8.
9. If today is Friday, what day of the week is it 16 days
from now?
[Link] 4, 2010, was a Sunday. What day of the week is
July 4, 2015?
[Link] A.M. or P.M., if it is 5 o’clock now what
time was it 57 hours ago?
THANK YOU!
I hope you learn something new today!
end

You might also like