Euclid(유클리드 알고리즘)

정수론

용어

1. 소수(prime number): 약수가 1 or 자기자신인 수
2. 서로소(coprime, relatively prime): 두 정수 a와 b의 공약수가 1인 경우
3. 약수와 배수: b = a*c → a|b or c|b
4. 공배수
   • a|b이고 c|b → b는 a와 c의 공배수(common multiple)
   • 최소공배수: lcm (least common multiple)
5. 공약수
   • a|b이고 a|c → a는 b와 c의 공약수(common divisor)
   • 최대공약수: gcd (greatest common divisor)

유클리드에 사용되는 기본 정리

1. m, n, c가 정수일 때
   • 만약 c가 m, n의 공약수이면 c|(m+n) (c는 m+n의 약수)
   • 만약 c가 m, n의 공약수이면 c|(m-n)
   • 만약 c|m이면 c|m∙n
2. 두 정수 a(≥0)와 b(>0)가 있을 때
   • a = b∙q+r(0 ≤ r< b) 이면 gcd(a,b) = gcd(b,r)
3. a, b가 양의 정수이면
   • gcd(a,b) = a∙x + b∙t를 만족하는 정수 s, t 존재
   • 확장된 유클리드 알고리즘에 사용되는 정리

유클리드 알고리즘

• 정리 2에 근거하여 gcd를 빠르게 찾는 알고리즘
  • gcd(a,b) = gcd(b, a mod b(=r))
  • gcd(385, 175) = gcd(175, 35) = gcd(35, 0) = 35
  • gcd(15, 8) = gcd(8, 7) = gcd(7, 1) = gcd(1, 0) = 1
• 코드 2가지 방법

int gcd(int a,int b)
    if (b == a) return a;
    return gcd(b, a % b);

int gcd(int a, int b) {
    int r1 = a, r2 = b, r;
    while (r2 > 0) {
        int q = r1 / r2; // q는 몫
        r = r1 - q * r2; // r은 a%b
        r1 = r2, r2 = r;
    }

    return r1;
}

• 2번째 코드는 확장된 유클리드 알고리즘에서 응용된다.

확장된 유클리드 알고리즘

• 정리 3의 gcd(a,b) = a∙s+ b∙t를 만족하는 정수 s, t를 찾아준다.

int extendEuclid(int a, int b) {
    int r1 = a, r2 = b, r;
    int s1 = 1, s2 = 0, s;
    int t1 = 0, t2 = 1, t;

    while (r2 > 0) {
        int q = r1 / r2; // q는 몫
        r = r1 - q * r2; // r은 a%b
        r1 = r2, r2 = r;

        s = s1 - q * s2;
        s1 = s2, s2 = s;

        t = t1 - q * t2;
        t1 = t2, t2 = t;
    }

    s = s1, t = t1;

    return r1;

}

정리 4 (디오판토스 방정식)

• a, b, c가 정수일 때, a∙x + b∙y= c 를 만족하는 정수 x, y가 존재 <-> gcd(a,b)|c
  • 2∙x + 4∙y = 7 일 때, 2와 4는 짝수로 이 식을 만족하는 x, y는 존재하지 않는다.
• 85∙x + 34∙y = 51 을 만족하는 x, y를 구하라
  1. 확장된 유클리드 알고리즘 이용: gcd(85, 34) = 17 = (85)∙(1) + 34∙(-2)
  2. 17|51 성립. 즉, 51/17 = 3
  3. 따라서, (85)∙(1)∙(3) + 34∙(-2)∙(3) = (17)∙(3) 만족
  4. x = (1)∙(3) = 3, y = (-2)∙(3) = -6

합동식

• ax ≡ b (mod n) 을 만족하는 x?
  • 정수 a, b, n이 주어지고 a∙x를 n 으로 나눌 때 나머지가 b가 되는 x 값
    • 3x ≡ 1 (mod 5) 를 만족하는 x는 { … -8, -3, 2, 7, 12, …}
• 5x ≡ 4 (mod 7)
  • 5x = 4 + 7y라는 의미 → 5x + 7y = 4: 확장된 유클리드 알고리즘 이용
    1. gcd(5, 7) = 1 = 5∙(3) + 7∙(-2)
    2. 1의 각 변을 4로 곱하면 4 = 5∙(12) + 7∙(-8)
    3. 따라서 x는 12, 12가 7보다 크므로 12 % 7 = 5로 최초 x 값은 5
    4. … 5 12 19 … 가 x

정리 5

1. a ≡ b (mod n) and c ≡ d (mod n) → a + c ≡ b + d (mod n) and ac ≡ bd(mod n)
2. ac ≡ bc (mod n) and gcd(c,n) = 1 → a ≡ b (mod n)
3. a ≡ b (mod n) → am ≡ bm (mod n) for all positive integers m.
4. a ≡ b (mod mn) → a ≡ b (mod m) and a ≡ b (mod n)
5. For c ≠ 0, ac ≡ bc(mod n) ↔ a ≡ b (mod (n/gcd(c,n))
   • 6x ≡ 8 (mod 10) → 3x ≡ 4 (mod 5)
6. a ≡ b (mod m), a ≡ b (mod n), and gcd(m, n)=1 → a ≡ b (mod mn)

정리 6 (정리 4)

• ax ≡ b (mod n) 을 만족하는 x가 존재 <-> gcd(a,n) | b

참고사항

• 모듈러 연산 참고