Modulo Operation
모듈로 연산
- Operand \(A, B\)에 대해,
\(A \;\mathrm{mod}\; B\) 는 \(A\)를 \(B\)로 나누었을 때의 나머지를 구하는 연산을 의미한다.
ex) \(5 \;\mathrm{mod}\; 3 = 2\)
ex) \(79 \;\mathrm{mod}\; 2 = 1\)
- 즉, \(A \;\mathrm{mod}\; B\)의 값은 반드시 \(0\) 이상, \(B\) 미만의 값이 도출된다.
Congruent Expression (Congruence; 합동식)
\(a \equiv b \; \mathrm{(mod \; p)}\)
\(\iff a \equiv b \; \mathrm{(p)}\)
\(\iff a \; \mathrm{mod} \; p \; = \; b \; \mathrm{mod} \; p\)
(단, \(a, b \in \mathbb{Z}\))
- 위 식을 "\(a\)와 \(b\)는 법 \(p\)에 대해 합동이다."라 읽는다.
- 두 정수 \(a, b\)에 대하여 \(|a - b|\) 가 \(p\)의 배수일 때를 의미하는 식이다.
- 달리 표현하면 \(a\)를 \(p\)로 나누었을 때의 나머지와 \(b\)를 \(p\)로 나누었을 때의 나머지가 같음을 의미하는 식이다.
Congruent Equation (합동방정식)
\(f(x) \equiv 0 \; (\mathrm{mod} \; p)\) : \(n\)차 합동방정식
\(f(x)\) : 정수를 계수로 하는 \(n\)차 다항식
\(x\) : \(n\)차 합동방정식을 만족시키는 해
Example. \(x^2 - 1 \equiv 0 \; (\mathrm{mod} \; 8)\\
x = 1, 3, 5, 7 \cdots\)
Definition of Modulo Operation
\(A \equiv B \; (\mathrm{mod}\; C)\\
\iff A \;\mathrm{mod}\; C = B \;\mathrm{mod}\; C\\
\iff C \; | \; (A-B)\\
\iff A = B + k \cdot C\)
Properties of Modulo Operation
\((A + B + C) \;\mathrm{mod}\; M\\
= (A \;\mathrm{mod}\; M + B \;\mathrm{mod}\; M + C \;\mathrm{mod}\; M) \;\mathrm{mod}\; M\)
\((A \cdot B) \;\mathrm{mod}\; C\\
= (A \;\mathrm{mod}\; C * B \;\mathrm{mod}\; C) \;\mathrm{mod}\; C\)
\(A^B \;\mathrm{mod}\; C\\
= (A \;\mathrm{mod}\; C)^B \;\mathrm{mod}\; C\)
\(a \equiv a \;(\mathrm{mod}\; m) \qquad (\forall a, \, a \in \mathbb{Z})\)
\(a \equiv b \;(\mathrm{mod}\; m) \iff b \equiv a \;(\mathrm{mod}\; m)\)
\(a \equiv \;(\mathrm{mod}\; m), b \equiv c\;(\mathrm{mod}\; m) \quad \to \quad a \equiv c \;(\mathrm{mod}\; m)\)
\(a \equiv b \;(\mathrm{mod}\; m), c \equiv d \;(\mathrm{mod}\; m) \to a \pm c \equiv b \pm d \;(\mathrm{mod}\; m)\)
\(a \equiv b \;(\mathrm{mod}\; m), c \equiv d \;(\mathrm{mod}\; m) \to ac \equiv bd \;(\mathrm{mod}\; m)\)
\(a \equiv b \;(\mathrm{mod}\; m) \to a^k \equiv b^k \;(\mathrm{mod}\; m)\)
\(ab \equiv ac \;(\mathrm{mod}\; m), d = gcd(a, m) \to b \equiv c \;(\mathrm{mod}\; {m \over d})\)
\(a \equiv b \;(\mathrm{mod}\; m), m \equiv 0 \;(\mathrm{mod}\; n) \to a \equiv b \;(\mathrm{mod}\; n)\)
\(a \equiv b \;(\mathrm{mod}\; m), d > 0\)이 \(a, b, m\)의 공약수 \(\to {a \over d} \equiv {b \over d} \;(\mathrm{mod}\; {m \over d})\)
Theorem
양의 정수 \(m, n\)과
정수 \(a, b\)에 대하여
\(a \equiv b \; (\mathrm{mod} \; m)\) 이고, \(a \equiv b \; (\mathrm{mod} \; n)\)
\(\iff\)
\(a \equiv b \; (\mathrm{mod} \; \mathrm{lcm}(m, \; n))\)
이다.
pf)
1. \(a \equiv b \; (\mathrm{mod} \; m)\) 이고, \(a \equiv b \; (\mathrm{mod} \; n)\)
\(\to\)
\(a \equiv b \; (\mathrm{mod} \; \mathrm{lcm}(m, \; n))\)
a \equiv b (mod m) 이고 a \equiv b (mod n) 이면
m | b-a 이고 n | b-a 이므로
lcm(m, n) | b-a 이다.
따라서 a \equiv b (mod lcm(m, n)) 이다.
2. \(a \equiv b \; (\mathrm{mod} \; m)\) 이고, \(a \equiv b \; (\mathrm{mod} \; n)\)
\(\gets\)
\(a \equiv b \; (\mathrm{mod} \; \mathrm{lcm}(m, \; n))\)
a \equiv b (mod lcm(m, n)) 이면
lcm(m, n) | b-a 이므로
m | b-a 이고 n | b-a 이다.
따라서 a \equiv b (mod m) 이고 a \equiv b (mod n) 이다.
Reference: 모듈로 연산
(Khan Academy, URL)
Modulo Operation
모듈로 연산
- Operand \(A, B\)에 대해,
\(A \;\mathrm{mod}\; B\) 는 \(A\)를 \(B\)로 나누었을 때의 나머지를 구하는 연산을 의미한다.
ex) \(5 \;\mathrm{mod}\; 3 = 2\)
ex) \(79 \;\mathrm{mod}\; 2 = 1\)
- 즉, \(A \;\mathrm{mod}\; B\)의 값은 반드시 \(0\) 이상, \(B\) 미만의 값이 도출된다.
Congruent Expression (Congruence; 합동식)
\(a \equiv b \; \mathrm{(mod \; p)}\)
\(\iff a \equiv b \; \mathrm{(p)}\)
\(\iff a \; \mathrm{mod} \; p \; = \; b \; \mathrm{mod} \; p\)
(단, \(a, b \in \mathbb{Z}\))
- 위 식을 "\(a\)와 \(b\)는 법 \(p\)에 대해 합동이다."라 읽는다.
- 두 정수 \(a, b\)에 대하여 \(|a - b|\) 가 \(p\)의 배수일 때를 의미하는 식이다.
- 달리 표현하면 \(a\)를 \(p\)로 나누었을 때의 나머지와 \(b\)를 \(p\)로 나누었을 때의 나머지가 같음을 의미하는 식이다.
Congruent Equation (합동방정식)
\(f(x) \equiv 0 \; (\mathrm{mod} \; p)\) : \(n\)차 합동방정식
\(f(x)\) : 정수를 계수로 하는 \(n\)차 다항식
\(x\) : \(n\)차 합동방정식을 만족시키는 해
Example. \(x^2 - 1 \equiv 0 \; (\mathrm{mod} \; 8)\\
x = 1, 3, 5, 7 \cdots\)
Definition of Modulo Operation
\(A \equiv B \; (\mathrm{mod}\; C)\\
\iff A \;\mathrm{mod}\; C = B \;\mathrm{mod}\; C\\
\iff C \; | \; (A-B)\\
\iff A = B + k \cdot C\)
Properties of Modulo Operation
\((A + B + C) \;\mathrm{mod}\; M\\
= (A \;\mathrm{mod}\; M + B \;\mathrm{mod}\; M + C \;\mathrm{mod}\; M) \;\mathrm{mod}\; M\)
\((A \cdot B) \;\mathrm{mod}\; C\\
= (A \;\mathrm{mod}\; C * B \;\mathrm{mod}\; C) \;\mathrm{mod}\; C\)
\(A^B \;\mathrm{mod}\; C\\
= (A \;\mathrm{mod}\; C)^B \;\mathrm{mod}\; C\)
\(a \equiv a \;(\mathrm{mod}\; m) \qquad (\forall a, \, a \in \mathbb{Z})\)
\(a \equiv b \;(\mathrm{mod}\; m) \iff b \equiv a \;(\mathrm{mod}\; m)\)
\(a \equiv \;(\mathrm{mod}\; m), b \equiv c\;(\mathrm{mod}\; m) \quad \to \quad a \equiv c \;(\mathrm{mod}\; m)\)
\(a \equiv b \;(\mathrm{mod}\; m), c \equiv d \;(\mathrm{mod}\; m) \to a \pm c \equiv b \pm d \;(\mathrm{mod}\; m)\)
\(a \equiv b \;(\mathrm{mod}\; m), c \equiv d \;(\mathrm{mod}\; m) \to ac \equiv bd \;(\mathrm{mod}\; m)\)
\(a \equiv b \;(\mathrm{mod}\; m) \to a^k \equiv b^k \;(\mathrm{mod}\; m)\)
\(ab \equiv ac \;(\mathrm{mod}\; m), d = gcd(a, m) \to b \equiv c \;(\mathrm{mod}\; {m \over d})\)
\(a \equiv b \;(\mathrm{mod}\; m), m \equiv 0 \;(\mathrm{mod}\; n) \to a \equiv b \;(\mathrm{mod}\; n)\)
\(a \equiv b \;(\mathrm{mod}\; m), d > 0\)이 \(a, b, m\)의 공약수 \(\to {a \over d} \equiv {b \over d} \;(\mathrm{mod}\; {m \over d})\)
Theorem
양의 정수 \(m, n\)과
정수 \(a, b\)에 대하여
\(a \equiv b \; (\mathrm{mod} \; m)\) 이고, \(a \equiv b \; (\mathrm{mod} \; n)\)
\(\iff\)
\(a \equiv b \; (\mathrm{mod} \; \mathrm{lcm}(m, \; n))\)
이다.
pf)
1. \(a \equiv b \; (\mathrm{mod} \; m)\) 이고, \(a \equiv b \; (\mathrm{mod} \; n)\)
\(\to\)
\(a \equiv b \; (\mathrm{mod} \; \mathrm{lcm}(m, \; n))\)
a \equiv b (mod m) 이고 a \equiv b (mod n) 이면
m | b-a 이고 n | b-a 이므로
lcm(m, n) | b-a 이다.
따라서 a \equiv b (mod lcm(m, n)) 이다.
2. \(a \equiv b \; (\mathrm{mod} \; m)\) 이고, \(a \equiv b \; (\mathrm{mod} \; n)\)
\(\gets\)
\(a \equiv b \; (\mathrm{mod} \; \mathrm{lcm}(m, \; n))\)
a \equiv b (mod lcm(m, n)) 이면
lcm(m, n) | b-a 이므로
m | b-a 이고 n | b-a 이다.
따라서 a \equiv b (mod m) 이고 a \equiv b (mod n) 이다.
Reference: 모듈로 연산
(Khan Academy, URL)
