정수론 : 모듈러, 소인수 분해, 최대공약수와 최소공배수, 에라토스테네스의 체

1. 모듈러 연산 (나머지 연산)

$a \equiv r \mod n$

$a$와 $r$을 $n$으로 나눈 나머지가 같다.

덧셈과 곱셈에서 나머지 연산의 순서는 상관 없습니다. 즉 더한 후 한꺼번에 나머지 연산을 한 값과, 각각의 항을 미리 나머지 연산을 한 후 더해서 나머지 연산을 한 값은 같습니다.

$12312312 + 234234234 \equiv 0 + 2 \equiv 2 \mod 4$

$7 * 9 \equiv 3 * 1 \equiv 3 \mod 4$

DP 다룰 때 자주 나옵니다.

2. 소인수 분해

어떤 수 $N$ 을 소인수 분해 하려면, 2부터 $\sqrt{N}$까지 원소들의 조건을 따지면서 분해하면 됩니다.

만약, $\sqrt{N}$보다 큰 소인수가 있다면, 그 소인수의 개수는 1개이며, 유일합니다.

ex) 44를 소인수 분해하기