斐蜀定理

目錄

• 前置芝士
• 寫在前面
  • 對于第一個推論的證明：
  • 對于第二個推論的證明：

國小數學

鳴謝：

初等數論筆記Part 2：中國剩餘定理

裴蜀定理

Q：啥叫飛鼠定理啊？

A：是斐蜀定理（捂臉

在數論中，裴蜀定理是一個關于最大公約數(或最大公約式)的定理--360百科

Q：說的啥啊？

1、對于正整數 \(a, b\) 存在整數 \(x, y\) 使得 \(\gcd(a, b) = ax +by\)

2、整數 \(a, b\) 互質的充要條件是存在整數 \(x, y\) 使得 \(ax + by = 1\)

簡單來說，我們設 \(d = \gcd(a, b)\)，那麼對于方程 \(ax + by = d\) ，一定存在一組整數解。并且對于方程 \(ax + by = z\)，如果滿足 \(d \mid z\)，那麼方程一定有整數解，否則無整數解。

（注：這裡 \(d \mid z\) 的意思是 \(z \bmod d = 0\)）

已知非零整數 \(a, b\)

記集合 \(S = \{ ax + by \mid x, y \in \mathbb{Z} 且 ax + by > 0\}\)

記整數 \(d = ax_0 + by_0\)

我們隻要證明 \(d = \gcd(a, b)\) 就證明了斐蜀定理，

設 \(a = dq + r\), 其中 \(q, r\) 是 \(a\) 模 \(d\) 的商和餘數，則有

\[r = a - dq = a - (ax_0 + by_0)q = a(1 - x_0q) + b(y_0q)

\]

因為我們用到的都是整數，是以不難看出 \(1 - x_0q\) 和 \(y_0q\) 也都是整數

是以 \(r \in S \cup \{ 0 \}\) ，（為啥要并上 \(0\) 尼？因為 \(r\) 表示餘數，餘數可以為 \(0\) 嘛）

我們又知道 \(0 \leqslant r < d\)，而 \(d\) 又是 \(S\) 中的最小元素，是以 \(r = 0\)

這意味着 \(d \mid a\)， 同理 \(d \mid b\)，又因為 \(\gcd(a, b) \mid d\) ，是以 \(d = \gcd(a, b)\)

證畢。

另外的，由集合 \(S\) 可以看出 \(x, y\) 的解不是唯一的，有無窮組系數 \((x, y)\) 都能滿足 \(\gcd(a, b) = ax + by\).并且，如果 \((x, y)\) 是一組系數，那麼所有系數可以表示為

\[(x + k · \frac{b}{\gcd(a,b)}, y - k·\frac{a}{\gcd(a,b)} ) \mid k \in \mathbb{Z}

再抄一遍

整數 \(a, b\) 互質的充要條件是存在整數 \(x, y\) 使得 \(ax + by = 1\)

利用反證法，

設 \(a, b\) 不互質，那麼 \(a, b\) 可以表示成 \(a = q \times \gcd(a, b), b = p \times \gcd(a, b)\)，帶入上面的式子，得到：

\[q \times \gcd(a, b) \times x + p \times \gcd(a, b) \times y = 1

兩邊同時除以 \(\gcd(a,b)\) 得到：

\[qx + py = \frac{1}{\gcd(a, b)}

顯然，如果 \(a, b\) 不互質，那麼式子右邊已經變成了一個小數，那麼方程一定不存在整數解。是以隻有當 \(a, b\) 互質時，該方程才有整數解.

順便我們可以得到：

對于方程 \(ax + by = z\), 隻有滿足 \(\gcd(a, b) \mid z\) ，方程才有整數解

證明：

設 \(d = \gcd(a, b), z = d \times q\)

對于方程 \(ax + by = d\) , 我們設有一組解為 \(x_0, y_0\), 那麼就有：

\[ax_0 + by_0 = d

兩邊同時乘 \(q\) 得：

\[ax_0 \times q + by_0 \times q = d \times q

\(\because z = d \times q\)

\(\therefore\) 方程 \(ax + by = z\) ，一定存在一組整數解為 \(x = x_0 \times q, y = y_0 \times q\) , 證畢

按照同樣的思路可以擴充到 \(n\) 元不定方程上

對于不定方程 \(a_1x_1 + a_2x_2 + a_3x_3 + … +a_nx_n = 1\)，隻有所有系數的 \(\gcd\) 為 \(1\) 時，方程才有整數解。

順便得到

所有系數 \(a_1, a_2, a_3 ,···,a_n\) 的最大公約數為 \(1\) 的充要條件是：滿足不定方程 \(a_1x_1 + a_2x_2 + a_3x_3 + … +a_nx_n = 1\)