[정수론] 약수, 배수, 최대공약수, 최소공배수와 관련된 알고리즘
공약수와 최대공약수(GCD), 공배수와 최소공배수(LCM), 유클리드의 호제법 (Euclidean Algorithm)나눗셈 정리 (Division Algorithm)임의의 정수 $a, b\ (b \neq 0)$에 대하여 $a = bq + r$, $0 \le r 파이썬 코드에서는 간단히 구할 수 있다.q = a // br = a % b 약수와 배수 (divisor and multiple)두 정수 $a, b \ (b \neq 0)$에 대하여 $b=ac$를 만족하는 정수 $c$가 존재할 때, $b$를 $a$의 배수(multiple)라 하고 $a$를 $b$의 약수(divisor) 또는 인수(factor)라 한다. 이때 "$a$는 $b$를 나눈다" 또는 "$b$는 $a$에 의하여 나누어떨어진다" 라고 하고, ..
2024. 8. 10.
[정수론] 오일러의 정리, 페르마의 소정리, 중국인의 나머지 정리, 윌슨의 정리
정수론 4대 정리: 오일러의 정리, 페르마의 소정리, 중국인의 나머지 정리, 윌슨의 정리 정수론 4대정리에 대해 간단히 정리한다. 자세한 내용이나 증명은 이후 포스팅 할 예정이다.여기서는 정리의 내용과 간단한 활용방법에 대해 알아본다.페르마의 소정리 (Fermat's little theorem)정수 $a$, 소수 $p$에 대하여 다음이 성립한다.\[ a^p \equiv p \pmod{p} \]$a$가 $p$로 나누어지지 않는 경우에(즉 $p \nmid a$, $\gcd(p, a)=1$) 다음이 성립한다.\[ a^{p-1} \equiv 1 \pmod{p} \] 역은 성립하지 않는다. 즉, 소수가 아닌 합성수 $p$인 경우에도 $a^{p-1} \equiv 1 \pmod{p}$인 경우가 존재한다.이런 $p$..
2024. 8. 6.
