본문 바로가기
정수론

나머지 정리

by kcj3054 2021. 11. 17.

임의의 자연수 n으로 어떤 수 k를 나눴을 때 몫과 나머지가 같아지는 경우는 나머지정리로 생각해보면된다.

 

 

몫과 나머지가 동일해진다면 (n * r) + r == k가 된다.   -> r(n +1) == k가 된다 고로 k는 n +1의 배수로 보면된다. 

여기서 조건이 하나 붙는데 r은 0 ~ n -1로 보면된다 

 

 

예시로  n에 3을 넣어보자 이런 경우 k는 n +1의 배수이니 4, 8, ..이된다  경우 r (3 + 1) = 4  ->>>> r조건은 0 ~ n-1이니  0 ~ 2

 

   4 / 3 => 몫은 1, 나머지도 1 정답!!!