初等數論--同余方程--二元一次不定方程的通解形式

博主是初學初等數論（整除+同余+原根），本意是想整理一些較難理解的定理、算法，加深記憶也方便日后查找；如果有錯，歡迎指正。
我整理成一個系列：初等數論，方便檢索。

• 不定方程：變量個數>方程個數

若二元一次不定方程$ax+by=n$有解，$x_0,y_0$為它的一組整數解，則通解為$$?\begin{array}{rlr}x& =& x_0+\frac{b}{(a,b)}?t\\ y& =& y_0?\frac{a}{(a,b)}?t\end{array}t\in Z$$

證明：

• 該形式確實是二元一次方程的解

將$x,y$代入原方程，得：
$$\begin{gathered} a(x_0+\frac{b}{(a,b)}?t)+b(y_0?\frac{a}{(a,b)}?t) \\ =a{x}_0+a\frac{b}{(a,b)}?t+b{y}_0?b\frac{a}{(a,b)}?t \\ =a{x}_0+b{y}_0 \\ =n \end{gathered}$$

• 二元一次不定方程的解都可以表達成這種形式

已知$$\{\begin{array}{r}ax+by=n\\ a{x}_0+b{y}_0=n\end{array}$$
聯立方程，相減得
$$\begin{gathered} a(x?x_0)+b(y?y_0)=0 \\ a(x?x_0)=?b(y?y_0) \\ \frac{a}{(a,b)}(x?x_0)=?\frac{b}{(a,b)}(y?y_0) \end{gathered}$$
因為$\frac{a}{(a,b)}?\frac{b}{(a,b)},且\frac{b}{(a,b)}\mid \frac{a}{(a,b)}(x?x_0),$所以$\frac{b}{(a,b)}\mid x?x_0$,即$x?x_0=\frac{b}{(a,b)}?t$
同理，$\frac{a}{(a,b)}\mid y?y_0$,即$y?y_0=?\frac{a}{(a,b)}?t$

總結

以上是生活随笔為你收集整理的初等数论--同余方程--二元一次不定方程的通解形式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。