유클리드 호제법

1. 개요

2. 증명

3. 활용

3.1. 최대공약수

3.2. 연분수

3.3. 소스 코드

3.3.1. C

#!syntax cpp
int Euclidean(int a, int b)
{
    int r = a % b;
    if (r == 0) {
      return b;
    }
    return Euclidean(b, r);
}

#!syntax cpp
int Euclidean(int a, int b)
{
    int r;
    while(r == 0) {
      r = a % b;
      a = b;
      b = r;
    }
    return a;
}

3.3.1.1. 숏코딩

#!syntax cpp
f(a,b){return b?f(b,a%b):a;}

3.3.2. Python

3.3.2.1. 반복문

#!syntax python
def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

3.3.2.2. 재귀문

#!syntax python
def Euclidean(a, b):
    if b == 0:
        return a
    return Euclidean(b, a % b)

3.3.3. Java

#!syntax java
int Euclidean(int a, int b) {
    if (b == 0)
        return a;
    return Euclidean(b, a % b);
}

3.4. 알고리즘으로서의 성능

4. 다항식에서의 호제법

4.1. 예시

5. 유한체에서

6. 관련 문서

• 최대공약수
• 나눗셈 정리
• 나머지 정리
• 베주 항등식