[JS] Modulo Operation

1. 더하기

(A + B) mod M = ((A mod M) + (B mod M)) mod M

const ans = ((A % M) + (B % M)) % M;

2. 빼기

(A - B) mod M = ((A mod M) - (B mod M)) mod M

const ans = ((A % M) - (B % M)) % M;

3. 곱하기

(A * B) mod M = ((A mod M) * (B mod M)) mod M

const ans = ((A % M) * (B % M)) % M;

4. 나누기

4.1. 페르소마 소정리 증명

페르소마 소정리: B^M-1 mod M = (B * B^M-2) mod M = 1, 단 M은 소수이고 B가 M의 배수가 아닌 경우

p-1의 집합 M = {1, 2, ... , p - 1}에서 모든 원소에 a를 곱한 aM = {a, 2a, ... , a(p - 1)}이 있을 때, M = aM mod p입니다. 예를 들어 p = 5, a = 2일 때, M = {1, 2, 3, 4}, aM = {2, 4, 6, 8}입니다. 이경우 aM mod p = {2, 4, 1, 3} = {1, 2, 3, 4}로 M = aM mod p입니다.

M = {1, 2, ... , p - 1}의 p - 1개 원소들은 모두 다르기 때문에 1에서 p의 수가 M에 전부 들어있습니다. 만약 {a, 2a, ... , a(p - 1)} mod p의 p - 1개 원소들도 서로 다르다면 M = aM mod p가 증명됩니다. 증명은 귀류법을 사용하면 간단합니다.

1. i !== j인데 ai mod p = aj mod p인 i, j가 존재한다고 가정합니다.
2. p가 소수이므로 양변을 a로 나눌 수 있습니다.
3. i mod p = j mod p가 되고, 1 <= i, j <= p - 1인 조건에서는 i = j가 되므로 1번 가정은 모순입니다.
4. 따라서 M = aM mod p입니다.

두 집합이 p에 대해 동일하므로 이 두 집합의 모든 각 원소를 곱한 값도 같을 것입니다.

1. 모듈로 곱하기 법칙에 의해서 {1, 2, ... , p - 1}! mod p = {a, 2a, ... , a(p - 1)}! mod p 입니다.
2. (1 * 2 * ... * (p - 1)) mod p = (a * 2a * ... * a(p - 1)) mod p로 전개됩니다.
3. 결국 (p - 1)! mod p = (a^p-1 * (p - 1)!) mod p이 성립합니다.
4. (p − 1)!과 p는 공통 인수를 가지지 않으므로 서로소입니다
5. (p − 1)!의 역원이 존재하며, 양변을 (p − 1)! 으로 나누면 a^p-1 mod p = 1 mod p이 성립됩니다.

4.2. 페르소마 정리를 이용한 나누기 모듈로

(A / B) mod M
= (A * B^-1) mod M
= ((A mod M) * (B^-1 mod M)) mod M
= ((A mod M) * (B^-1 mod M) * ((B * B^M-2) mod M )) mod M
= ((A mod M) * ((B^-1 * B * B^M-2) mod M)) mod M
= ((A mod M) * (B^M-2 mod M)) mod M

const ans = ((A % M) * (Math.pow(B, M - 2) % M)) % M;