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