Modulo(1)

나머지 연산

• 나눗셈의 식 a = bq + r은 a를 b로 나눌 경우 몫은 q, 나머지는 r이되는 관계를 표현.

\[q(몫) = \lfloor \frac{a}{b} \rfloor\] \[r(나머지) = a \ mod \ b = a - b (\lfloor \frac{a}{b} \rfloor)\]

3 ≡ 31(mod 7)
    3 mod 7 = 3
    31 mod 7 = 3

-31 ≡ 11(mod 7)
    -31 mod 7 = 4,  -35 ~ -31
    11 mod 7 = 4

-15 ≡ -50(mod 7)
    -15 mod 7 = 6,  -21 ~ -15
    -50 mod 7 = 6,  -56 ~ -50

• a,b가 정수이고 m이 양의 정수라 하자. 그러면 a ≡ b (mod m) 은 a mod m = b mod m과 필요 충분 조건이다.

합동의 기본정리

• m > 1이 고정되고 a, b, c, d를 임의의 정수라 할 떄, 다음 성직이 성립한다.
  • a ≡ a(mod m)
  • a ≡ b(mod m)이면 b ≡ a(mod m)이다.
  • a ≡ b(mod m)이고 b ≡ c(mod m) 이면 a ≡ c(mod b) 이다.
  • a ≡ b(mod m)이고 c ≡ d(mod m) 이면 a + c ≡ b + d (mod m) 이고 ac ≡ bd (mod m)이다.
  • a ≡ b(mod m)이면 a + c ≡ b + c (mod m)이고 ac ≡ bc (mod m) 이다.
  • a ≡ b(mod m)이면 모든 양의 정수 k에 대해 a^k ≡ b^k(mod m)이다.

7 ≡ 2(mod 5)와 11 = 1(mod 5)가 성립할 경우, 18과 77을 5로 나누었을 때 나머지를 각각 구하시오.

7 ≡ 2(mod 5), 11 ≡ 1(mod 5)

* a + c ≡ b + d (mod m)

18(mod 5)
    = ( 7 + 11 = 2 + 1( mod 5) ) = ( 18 = 3 mod 5 ) = 3

77(mod 5)
    ≡ (77 = 2(mod 5)) = 2