유클리드 와 확장 유클리드 설명 (기초 수론)

두 개의 정수 a, b, a, b 의 최대 공약수 를 알 고 있 습 니 다. 우 리 는 다음 과 같은 방법 이 있 습 니 다.
1. 순환 i 는 mind (a, b) ~ 1 에서 첫 번 째 로 a 와 b 에 의 해 정 제 될 수 있 는 i 는 a 와 b 의 최대 공약수 이다.
2. 전전 상감 법
3. 전전 상 제법, 즉 유클리드.
알고리즘 1: 폭력 구 해

int gcd(int a,int b)  
{
    int ans;
    for(int i = min(a,b); i > 0; i--)
    {
        if(a%i==0 && b%i==0)
        {
            ans = i;
            break;
        }
    }
    return ans;
}

폭력 구 해 는 a, b 가 비교적 크 고 서로 채식 할 때 매우 시간 이 걸린다.
알고리즘 2: 전전 상감 법
4. 567913. 전전 상감 법 은 매우 좋다.
알고리즘 3: 전전 상 제법

int gcd(int m,int n)
{
    if (m==n) return m;
    if(m

귀속 서법 사진 은 매우 간단 하 다. 내 가 좋아한다.❤ ω ❤)라 고 적 었 다.
매일 전전 상 제법 을 쓰 지만 왜 이러 는 지 는 확실히 증명 되 지 않 았 다.
유클리드 알고리즘 증명:
만약 우리 가 정수 a 와 b 의 최대 공약수 를 요구한다 면, 특별한 성명 이 없 으 면, 아래 에 나타 난 소문 자 는 모두 정 수 를 대표 합 니 다.
q = a / b (이 나눗셈 은 정 제 를 가리 키 는 말) 는 상, r = a% b 는 나머지 이 고 d = gcd (a, b), 즉 a, b 의 최대 공약 수 는 d 이다.
... 하면 a = b*q + r
d 는 a 와 b 의 최대 공약수 이기 때문에 정수 c1, c2 는 a = c1 * d 가 존재 합 니 다. ,    b = c2*d
a = b * q + r 때문에,
그래서 r = a - b * q 
  = c1*d - c2*d*q
  = d*(c1-c2*q)
c1, c2, q 는 모두 정수 이기 때문에 c1 - c2 * q 도 정수 입 니 다. 위의 식 에서 r / d = c1 - c2 * q 를 볼 수 있 습 니 다.
이 를 통 해 알 수 있 듯 이 d 도 r 의 인자 이다. d 는 b 의 인자 이기 때문에 d 는 b 와 r 의 공인 자 이지 만 지금 은 d 를 끝까지 증명 해 야 한다.
b 와 r 의 최대 공약수 아 닙 니까?
계속 증명 하 세 요. c 가 b 와 r 의 임 의 공약수 라 고 가정 하면 b 는 c 의 배수 이 고 r 도 c 의 배수 입 니 다. a = b * q + r 에서
a 는 반드시 c 의 배수 임 을 알 수 있 기 때문에 c 도 a, b 의 인자 이지 만 a, b 의 최대 공인 자 는 d 이기 때문에 c < = d.
또한 c 는 b 와 r 의 임 의 공약수 이기 때문에 c 는 b 와 r 의 최대 공약수 일 수 있 고 c 는 d 보다 작다.
d 는 b 와 r 의 공약수 이기 때문에 d 는 b 와 r 의 최대 공약수 이다.
따라서 d = gcd (b, r).
다시 말 하면 d = gcd (a, b) = gcd (b, r) = gcd (b, a% b)
위의 식 은 재 귀 과정 을 나타 내 는데 재 귀 가 끝 나 는 조건 은 0 이 고 이때 마지막 나머지 는 0 이다.
유클리드 알고리즘 추론: 유클리드 확장
d = gcd (a, b) 가 있 으 면 x 와 y 가 x + by = d 를 사용 합 니 다.
이 점 을 우 리 는 역 추 유클리드 알고리즘 을 통 해 얻 을 수 있다.
우 리 는 유클리드 알고리즘 이 마지막 까지 실 행 된 것 을 안다.
a = gcd(a,b) = d，  b = 0
x1 = 1 이 존재 합 니 다. y1 = (임 의 수, b 는 0 이기 때문에 우 리 는 보통 0 을 취한 다), a * x1 + b * y1 = d 의 성립 을 만족시킨다. 
gcd (a, b) = gcd (b, r) 때문에
우 리 는 마지막 단계 에서 얻 을 수 있다 는 것 을 안다.
b*x1 + r*y1 = d;
r = a% b 아래 식 가 져 오기
b*x1 + a%b*y1 = d;
b*x1 + (a-a/b*b)*y1 = d
b*x1 + a*y1 - (a/b)*y1*b = d
a*y1 + (x1-(a/b)*y1)*b = d
풀이:
x2 = y1       y2 = x1 - (a/b)*y1;
마찬가지 로 우 리 는 인터넷 에서 계속 추천 할 수 있 습 니 다. 반드시 해 x 가 존재 한 다 는 것 을 알 수 있 습 니 다. y 는 x + by = gcd (a, b) 를 사용 합 니 다.
반드시.
알고리즘 구현: 유클리드 알고리즘 에서 작은 개선

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

본문 부분 은 이라는 책 을 참고 한 다 는 것 을 증명 한다.