---
# System prepended metadata

title: '歐幾里得算法,擴展歐幾裡得算法'
tags: [Algorithm]

---

# 歐幾里得算法,擴展歐幾裡得算法

###### tags: `Algorithm`

## 歐幾裡得算法
### gcd(a,b)=gcd(b,r)

> 已知 a\b=q...r 
> a=bq+r

d=a,b 的公因數 
 → d 為 a-bq的因數
 → d 為 r 的因數
 → a,b 的公因數為r的因數
 :::info
 gcd(a,b)=gcd(b,r)
 :::
 
 ### 輾轉相除法
 
 > (703,407)
 
 703 / 407 = 1 ... 296

  → 求 (407,296)
  
 > (407,296)
 
 407 / 296 = 1...111
  
 > 求 (206,111)
.
.
.

## 擴展歐幾裡得算法
>a,b ∈ Z
必存在整數 x,y 使ax+by = gcd(a,b)
求x,y

```
設 a*x1 + b*y1 = gcd(a, b) (1)

   b*x2 + a%b * y2 = gcd(b, a%b)(2)

又    gcd(a,b) = gcd(b,a%b)

所以有a*x1 + b*y1 = b*x2 + (a - a/b * b)*y2  (此處的'/'為向下取整除)

化簡有a*x1 + b*y1 = a*y2 + b* (x2 – a/b * y2)
x1 = y2, y1 = (x2 - a/b * y2)
```

:::info
結論:
x1 = y2, y1 = (x2 - a/b * y2)
:::

```cpp=
void exGcd (int a, int b, int &x, int &y)
{
    int t;
    if (b==0) x = 1, y = 0;
    else      gcd(b,a%b,x,y), x = y, y = t-a/b*y;
}
```
