알고리즘/수학
2021. 3. 11.
기초 정수론1
PS에 필요한 기초적인 정수론을 다뤄 봅시다. 저는 수학을 잘 하지는 못합니다. 그래서 이 글에서는 각 주제에 해당하는 내용에 대해 간단히 설명만 하고, 엄밀한 증명은 하지 않을 예정입니다. 단순히 "이런 것들이 있다" 정도로만 봐 주시면 좋을 것 같습니다. 자세한 내용이나 증명은 다른 글을 참조해주세요. 유클리드 알고리즘 두 양의 정수 \(A, B\)의 최대공약수를 구해봅시다. \(\gcd(A, B) = g\)라고 하면, 다음과 같이 나타낼 수 있습니다. $$A = ga, B = gb$$ \(a\)와 \(b\)는 서로소입니다. \(A\)를 \(B\)로 나눴을 때 몫과 나머지를 각각 \(q, r\)이라고 해 봅시다. $$A = Bq+r$$ 위의 식을 대입해 봅시다. $$ga = gbq+r$$ $$r = ..