모듈로 연산 (Modular Arithmetic)

정의

Let a, r, m ∈ Z and m > 0

Then

a ≡ r mod m      r ÷ m = 몫 ⋯ a

if m divides (a-r), i.e., m|(a - r)

 

 

주요 특성

a ≡ b mod n  ⇔  b ≡ a mod n

    n|(a - b)               n|(b - a)                ∵ b - a = - (a - b)

a ≡ b mod n and b ≡ c mod n ⇒ a = c

                               c ≡ b mod n

(a + b) mod n = ((a mod n) + (b mod n)) mod n

(a - b) mod n = ((a mod n) - (b mod n)) mod n

(a x b) mod n = ((a mod n) x (b mod n)) mod n

 

We can prove them by definition of modulo arithmetic

 

∙ 교환

(a + b) mod n = (b + a) mod n

(a x b) mod n = (b x a) mod n

 

∙ 결합

((a + b) + c) mod n = (a + (b + c)) mod n

((a x b) x c) mod n = (a x (b x c)) mod n

 

∙ 분배

(a x (b + c)) mod n = ((a x b) + (a x c)) mod n

 

 

예시

3^8 mod 7 = 3^2 x 3^2 x 3^2 x 3^2    mod 7

                    = 9 x 9 x 9 x 9

                    = 2 x 2 x 2 x 2    ∵ 9 mod 7 = 2

                    = 16

                    = 2

                    = 2 mod 7

 

 

 

 

 

* Reference

https://youtu.be/MAd3IJEaMls?feature=shared