모듈로 계산기

음수에 대한 두 가지 규칙

양의 피연산자에서는 모든 규칙이 일치합니다: 17 mod 5 = 2. 음수에서는 언어마다 다릅니다:

내림 나눗셈: 몫이 −∞ 쪽으로 반올림됩니다. 나머지는 항상 제수의 부호를 가집니다: b와 같은 부호. 버림 나눗셈: 몫이 0 쪽으로 반올림됩니다. 나머지는 피제수의 부호를 가집니다: a와 같은 부호.

a = -17, b = 5의 경우:

• 버림: q = -3(0 쪽으로 반올림), r = -17 − (-3)·5 = -2.
• 내림: q = -4(-∞ 쪽으로 반올림), r = -17 − (-4)·5 = 3.

규칙을 고려하면 둘 다 옳습니다. 언어에 맞춰 고르세요.

모듈로가 등장하는 곳

• 시간. 한 시간의 분, 요일, 하루의 초, 모두 mod 산술입니다.
• 해시 테이블. hash(key) mod table_size가 버킷을 고릅니다.
• 라운드 로빈 스케줄링. task_i mod worker_count가 작업을 할당합니다.
• 암호학. RSA와 디피-헬먼은 거대한 소수와 함께 mod n 위에 세워집니다.
• N행마다. SQL에서: WHERE id % 3 = 0.
• 짝수/홀수 검사. n mod 2 == 0이면 짝수.
• 번갈아 나오는 패턴. 행 줄무늬, 한 칸 건너 색칠.
• 순환 버퍼. (index + 1) mod size가 감싸 돌아옵니다.

유용한 항등식

• (a + b) mod n = ((a mod n) + (b mod n)) mod n
• (a · b) mod n = ((a mod n) · (b mod n)) mod n
• (a^k) mod n은 O(log k)의 빠른 모듈러 거듭제곱으로 계산할 수 있습니다, 큰 수 암호에 핵심입니다.
• 모든 정수 a에 대해 a mod 1 = 0.
• a mod a = 0.

소수 모듈로

실수의 경우 자연스러운 정의는 a mod b = a − b · floor(a/b)입니다. 7.5는 정확한 배수이므로 7.5 mod 2.5 = 0. 7.6 mod 2.5 = 0.1.

JavaScript의 % 연산자는 실수에서 작동하고, Python의 fmod는 버림 실수 mod를, Python의 %는 내림 실수 mod를 합니다.

풀이 예제

• 100 mod 7: 100 = 14·7 + 2, 나머지 2.
• 25 mod 4: 25 = 6·4 + 1, 나머지 1.
• -10 mod 3(내림): -10 = -4·3 + 2, 나머지 2. (버림이면 -1.)
• 17.5 mod 5: 17.5 = 3·5 + 2.5, 나머지 2.5.