python/TangDou/AcWing/NumberTheory/二元一次不定方程的通解形式.md

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

• 不定方程：变量个数>方程个数

若二元一次不定方程ax + by = n有解，x_0, y_0为它的一组整数解，则通解为：

\large 
\left\{\begin{matrix}
 x=x_0 + \frac{b}{(a,b)} \cdot t\\ 
 y=y_0-\frac{a}{(a,b)}\cdot t 
\end{matrix}\right.
\ \ \ \ t \in  Z

​ 证明：

• 该形式确实是二元一次方程的解 将x,y代入原方程，得： \large \displaystyle a(x_0+\frac{b}{(a,b)}\cdot t) + b(y_0-\frac{a}{(a,b)}\cdot t) \large \displaystyle =ax_0+a\frac{b}{(a,b)}\cdot t + by_0-b\frac{a}{(a,b)}\cdot t \large \displaystyle =ax_0+by_0 \large \displaystyle =n

• 二元一次不定方程的解都可以表达成这种形式 已知

  \large 
  \left\{\begin{matrix}
  ax+by=n
  \\ 
  ax_0+by_0=n
  \end{matrix}\right.
  

  联立方程，相减得：

  \large a(x-x_0)+b(y-y_0)=0

  \large a(x-x_0)=-b(y-y_0)

  \large \frac{a}{(a,b)}(x-x_0)=-\frac{b}{(a,b)}(y-y_0)

  \large  \because \frac{a}{(a,b)}\nmid \frac{b}{(a,b)}

  且

  \large  \frac{b}{(a,b)} | \frac{a}{(a,b)}(x-x_0)

  \large  \therefore \frac{b}{(a,b)} | x-x_0

  即

  \large   x-x_0=\frac{b}{(a,b)}\cdot t

  同理,\large \displaystyle \frac{a}{(a,b)}|y-y_0,即

  \large  y-y_0=-\frac{a}{(a,b)}\cdot t

  \huge Q.E.D