합동식

합동식은 두 정수 a,b를 각각 정수 m으로 나눴을 때 나머지가 같은지를 판별하는 식입니다. a와 b각각을 m으로 나눈 나머지가 같을 때, 수학적으로 a와 b가 modm에 대해 합동(congruent)이라고 표현합니다.

예를 들어, 7과 17은 10으로 나눈 나머지가 같기 때문에 7과 17은 mod 10에 대해 합동이며 기호로는 7≡17(mod10)로 나타냅니다. 반대로 12와 5는 3으로 나눈 나머지가 다르므로 12와 5는 mod 3에 대해 합동이 아니며, 기호로는 12≡5(mod3)로 나타냅니다.

a,b가 modm에 대해 합동일 경우 modm각각에 정수 x를 더하거나 빼거나 곱해도 여전히 합동입니다.

a≡b(modm)⇒⎩⎨⎧a+x≡b+x(modm)a−x≡b−x(modm)ax≡bx(modm)

그러나 나눗셈에 대해서는 성립하지 않습니다.

a≡b(modm)⇒xa≡xb(modm)

합동식에서 곱셈의 역원

정수 a,m에 대해 a×b≡1(modm)을 만족하는 b를 modm에 대한 a의 곱의 역원이라고 부르며, a−1로 표기합니다.

예를 들어 2×4=8≡1(mod7)이므로 mod7에서 2에 대한 역원은 4입니다.

역원은 a와 m이 서로소일 때에만 존재합니다.