백준 등 프로그래밍 문제에서 계산한 결과를 10^9+7로 나눈 나머지를 출력하라 지시하는 경우가 많은데, 오버플로우를 막기 위함인건 알았지만 그 값을 소수로 사용하는 이유는 오늘 처음 알았다. 그 값이 소수여야 모듈러 곱셈 역원을 구할 수 있기 때문이다. (10^7+9는 10자리인 첫 번째 소수이기 때문에 자주 사용된다고 한다.)
풀어 말하자면 실수에서 2를 나누는 것과 1/2를 곱하는 것 대신 군 안에서는 2를 나누는 대신 모듈러 했을 때의 곱셈 역원인 정수를 대신 곱해줄 수 있는데, 모듈러하는 값이 소수일 때만 곱셈 역원이 항상 존재한다.
예시: 팩토리얼, 조합 경우의 수와 같이 매우 큰 수를 계산할 때 곱셈 역원을 사용할 수 있음
C(n, k) = n! x (k!)^-1 x ((n-k)!)^-1 (mod p)소수가 아닌 경우 아래같은 케이스가 있음 e.g. (m = 8, a = 1, b = 2) 1 / 2 mod{8}을 구할 수 없음
- x: 2x mod 8
- 0: 0
- 1: 2
- 2: 4
- 3: 6
- 4: 0 ... 반복
https://www.geeksforgeeks.org/dsa/modulo-1097-1000000007 https://www.quora.com/What-exactly-is-print-it-modulo-10-9-+-7-in-competitive-programming-web-sites
