합동식 (모듈로 modulo 연산)

 

 

 

개요

• 합동식
  
  • \( a \equiv b \pmod n\)
  • a와 b는 n으로 나눈 나머지가 같다는 뜻

 

시계와 합동식

• 지금이 9시인데, 5시간 후에는 몇시인가?
  
  • 익숙한 덧셈으로 하자면 14시라고 해야하겠지만, 2시라고 한다.
  • \(9+5 \equiv 2 \text{ mod } 12\)
  • 이것의 바로 합동식의 개념

 

기본적인 성질

• \(a_1 \equiv b_1 \pmod n\) , \(a_2 \equiv b_2 \pmod n\) 이면, 다음과 같은 합동식이 성립함.