Fermat's Little Theorem & Euler's Theorem
Fermat's Little Theorem. p가 소수이고, a가 a가 p로 나누었을 때 나누어 떨어지지 않는 수라면, a^(p -1) ≡ 1 (mod p) 위 식이 성립한다. 페르마 본인은 이 정리의 증명을 쓰지 않았지만, 이 정리의 증명은 어렵지 않다. 먼저, p로 나누어 떨어지지 않는 수는, p가 소수일 때 p - 1만큼 존재한다. 또, 재미있는 사실은 1에서 p - 1까지의 수를 p로 나누었다면, 여기에 어떤 수를 곱하더라도 그 나머지는 이 집합에 포함된다. 이것을 다시 쓰면, 1, 2, 3, ... (p - 1) (mod p)는, a, 2a, 3a, ... (p - 1)a (mod p)와 합동이다. 즉, 1, 2, 3, ... (p - 1) (mod p) ≡ a, 2a, 3a, ... (p - ..
더보기