Transcript a ≡ b (mod n)

CONGRUENCES
AND
MODULAR
ARITHMETIC
Congruence and Modular
Arithmetic
Definition: a is congruent to b mod n means that n∣a-b, (ab) is divisible by n.
Notation:
Ex.
a ≡ b (mod n)
, a, b, n ∈ I, n ≠ b
42 ≡ 30 (mod 3)
Since,
3 ∣ 42 – 30
a ≡ b (mod n), it means that n ∣ a – b
Ex.
3 ≡ 4 (mod 5)
Congruence and Modular
Arithmetic
If two numbers a and b have the property that their
difference a-b is divisible by a number n (ex. (a-b) ∣ n is an
integer), then a and b are said to be "congruent modulo n."
The number n is called the modulus, and the statement "a is
congruent to b (modulo n)" is written mathematically as
a ≡ b (mod n)
Congruence and Modular
Arithmetic
If a – b is not divisible by n, then it is said that "a is
not congruent to b (modulo n)," which is written as
a ≡ b (mod n)
Proposition
Proposition: Congruence mod m is an equivalence relation:
Equivalence relation is a reflexive (every element is in the
relation to itself), symmetric (element a has the same relation to
element b that b has to a), and transitive (a is in a given relation
to b and b is in the same relation to c, then a is also in that
relation to c) relationship between elements of a set.
Proposition: Any relation is called an equivalence relation if it
satisfied the following properties:
1. Reflexivity (every element is in the relation to itself)
a ≡ a (mod n) for all a
Ex.
3 ≡ 3 (mod 5)
2. Symmetry (element A has the same relation to element B that B
has to A),
If a ≡ b (mod n), then b ≡ a (mod n)
Ex.
10 ≡ 7 (mod 3), then 7 ≡ 10 (mod 3)
3.Transitivity
If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)
Ex. 20 ≡ 4 (mod 8), then 4 ≡ 12 (mod 8), then 20 ≡ 12 (mod 8)
Properties
1. Equivalence: a ≡ b (mod 0) → a ≡ b (which can be
regarded as a definition)
Ex.
18 ≡ 6 (mod 0)
0 ∣ 18 – 6
2. Determination: either a ≡ b (mod n) or a ≡ b (mod n)
Ex.
3. Reflexivity:
Ex.
30 ≡ 3 (mod 9) or 14 ≡ 5 (mod 2)
9 ∣ 30 – 3
2 ∣ 14 – 5
a ≡ a (mod n)
7 ≡ 7 (mod 1)
1∣7–7
Properties
4. Symmetry: a ≡ b (mod n), then b ≡ a (mod n)
Ex.
20 ≡ 2 (mod 6), then 2 ≡ 20 (mod 6)
6 ∣ 20 – 2 , then
6 ∣ 2 – 20
5. Transitivity:
a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)
Ex. 16 ≡ 4 (mod 2) and 4 ≡ 8 (mod 2), then 16 ≡ 8 (mod 2)
2 ∣ 16 – 4 and 2 ∣ 8 – 4 , then 2 ∣ 16 – 8
6. a ≡ b (mod n) → (k)a ≡ (k)b (mod n)
Ex. 25 ≡ 5 (mod 10) → (2)25≡ (2)5 (mod 10)
10 ∣ 25 – 5 → 10 ∣ 50 – 10
Properties
7. a ≡ b (mod n) → am ≡ bm (mod n), n ≥ 1
Ex.
42 ≡ 12 (mod 3)
3 ∣ 16 – 1
8. a ≡ b (mod n1) and a ≡ b (mod n2) → a ≡ b (mod [n1, n2] ),
where [n1, n2] is the LCM
Ex.
15 ≡ 3 (mod 4) and 15 ≡ 3 (mod 6)
→ 15 ≡ 3 (mod [4, 6] )
→ 15 ≡ 3 (mod 12)
→ 12 ∣ 15 – 3
Properties
n
9. ak ≡ bk (mod n) → a ≡ b (mod (k,n)
),
where (k, n) is the HCF
Ex.
2
15 (4) ≡ 13 (4) (mod 2) → 15 ≡ 13 (mod (4,2) )
60 ≡ 52 (mod 2)
→ 15 ≡ 13 (mod
2
2
→ 15 ≡ 13 (mod 1)
2 ∣ 60 – 52
→
1 ∣ 15 – 13
)
EXERCISE !!
Exercise
1. Give an example for transitivity property “a ≡ b
(mod n) and b ≡ c (mod n), then a ≡ c (mod n)”.
2. Find 3 numbers of “a”
a ≡ 10 (mod 3), then 10 ≡ a (mod 3)
3. Find x
24 ≡ 8 (mod x), then 8 ≡ 18 (mod x),
then 24 ≡ 18 (mod x)
4. Find 3 numbers of “b”.
38 ≡ b (mod 3) → (2)38≡ (2)b (mod 3)
Exercise
5. True or False
283 ≡ 53 (mod 3)
383 ≡ 53 (mod 3)
255 ≡ 6 (mod 7)
6. Solve the following.
42 ≡ 6 (mod 4) and 42 ≡ 6 (mod 9)
23 (12) ≡ 15 (12) (mod 4)
322 ≡ 83 (mod 6)

THANK YOU
Submitted by:
EP 4/1 Group 3
Chosita K. “2”
Hsinju
C. “3”
Nipawan P. “5”
Ob-Orm U. “11”
Submitted to:
Mr. Wendel Glenn Jumalon
