알고리즘/수학
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 = ..
