二元一次不定方程是指含有两个未知数，并且含有未知数的项的次数都是1的整式方程。

一般形式为\(ax + by = c\)，其中\(a\)、\(b\)、\(c\)是整数，且\(a\)、\(b\)不同时为\(0\).

二元一次不定方程有解的条件

根据裴蜀定理，对于二元一次不定方程\(ax + by = c\)，方程有整数解的充要条件是\((a,b)\mid c\)，其中\((a,b)\)表示\(a\)与\(b\)的最大公约数.

1. 裴蜀定理与二元一次不定方程的联系

二元一次不定方程\(ax + by=c\)（\(a\)、\(b\)、\(c\)是整数，且\(a\)、\(b\)不同时为\(0\)）有解的充分必要条件是\((a,b)\mid c\)，这里\((a,b)\)表示\(a\)和\(b\)的最大公因数，\(\mid\)表示整除。

裴蜀定理的内容是：对于任意两个整数\(a\)、\(b\)，存在整数\(x\)、\(y\)，使得\(ax+by=(a,b)\)。

例如，对于\(a = 6\)，\(b = 8\)，\((6,8) = 2\)，可以找到\(x=-1\)，\(y = 1\)，使得\(6\times(-1)+8\times1=2\)。

2. 证明有解条件

必要性证明（若方程\(ax + by=c\)有解，则\((a,b)\mid c\)）

设\(d=(a,b)\)，因为\(d\)是\(a\)和\(b\)的最大公因数，所以\(a = md\)，\(b = nd\)（\(m\)、\(n\)为整数）。

若方程\(ax + by=c\)有解，设解为\((x_0,y_0)\)，则\(ax_0+by_0=c\)，将\(a = md\)，\(b = nd\)代入可得\(mdx_0 + ndy_0=c\)，即\(d(mx_0+ny_0)=c\)，所以\(d\mid c\)，也就是\((a,b)\mid c\)。

充分性证明（若\((a,b)\mid c\)，则方程\(ax + by=c\)有解）

根据裴蜀定理，存在整数\(x_1\)、\(y_1\)，使得\(ax_1+by_1=(a,b)\)。

因为\((a,b)\mid c\)，所以存在整数\(k\)，使得\(c = k(a,b)\)。

那么\(ax_1\times k+by_1\times k=(a,b)\times k=c\)，即\(x = x_1k\)，\(y = y_1k\)是方程\(ax + by=c\)的一组解，所以方程有解。

3. 举例说明

对于方程\(3x + 6y = 5\)，计算\((3,6)=3\)，而\(3\nmid5\)，所以该方程无整数解。

对于方程\(4x + 6y = 2\)，\((4,6)=2\)，且\(2\mid2\)，所以该方程有整数解。可以通过求解得到一组特解\(x = -1\)，\(y = 1\)，进而得到通解来验证方程有解这一结论。

二元一次不定方程求解方法

观察法：当不定方程系数不大时，可通过观察直接找出一组特解。

例如方程\(3x + 4y = 10\)，通过观察可发现\(x = 2\)，\(y = 1\)是一组特解.

扩展欧几里得算法：对于方程\(ax + by = (a,b)\)，可以使用扩展欧几里得算法求出一组特解\(x_0\)，\(y_0\)，然后再根据有解的条件和通解公式求出方程\(ax + by = c\)的通解。具体步骤如下 ：

设\(a > b\)，执行辗转相除法的过程如下：

\((a,b)=\begin{cases}b, & a = 0\\(b, a\bmod b), & \text{otherwise}\end{cases}\)

在辗转相除的过程中，根据每一步的\(a\)、\(b\)值以及对应的\(x\)、\(y\)值，通过一定的递推关系求出最终的\(x_0\)、\(y_0\)。

例如，当\(a = 39\)，\(b = 15\)时，辗转相除过程为：

\(39,15\rightarrow15,9\rightarrow9,6\rightarrow6,3\rightarrow3,0\)

先考虑最后一个方程\(3x_0 = 3\)，可得\(x_0 = 1\)。

然后往上推，根据递推关系\(x_1 = y_0\)，\(y_1 = x_0 - \lfloor\frac{a_1}{b_1}\rfloor\times y_0\)，依次求出前面步骤中的\(x\)、\(y\)值，最终得到方程\(39x + 15y = 3\)的一组特解。

再根据方程\(ax + by = c\)有解时，\(c = k\times(a,b)\)，将求出的特解乘以\(k\)，得到方程\(ax + by = c\)的特解。

二元一次不定方程通解公式

1. 特解与通解的概念

对于二元一次不定方程\(ax + by=c\)（\(a\)、\(b\)、\(c\)是整数，且\(a\)、\(b\)不同时为\(0\)），特解是满足该方程的一组特定的整数解\((x_0,y_0)\)。而通解则是包含了该方程所有整数解的表达式。

2. 通解公式的推导

首先，根据裴蜀定理，方程\(ax + by=c\)有整数解的充分必要条件是\((a,b)\mid c\)（其中\((a,b)\)表示\(a\)和\(b\)的最大公因数）。

假设\((x_0,y_0)\)是方程\(ax + by=c\)的一个特解。设\(d=(a,b)\)，则\(a = d\cdot m\)，\(b = d\cdot n\)（\(m\)、\(n\)为整数）。

对于任意整数\(k\)，将\(x = x_0+nk\)，\(y = y_0 - mk\)代入原方程\(ax+by\)得：

\(a(x_0 + nk)+b(y_0 - mk)=ax_0 + ank+by_0 - bmk\)

因为\(ax_0+by_0 = c\)，且\(a = d\cdot m\)，\(b = d\cdot n\)，所以上式可化为\(c + dmnk - dmnk=c\)。

所以，方程\(ax + by=c\)的通解公式为\(\begin{cases}x = x_0+\frac{b}{d}k\\y = y_0-\frac{a}{d}k\end{cases}\)（\(k\in Z\)）。

3. 举例说明

例如，对于方程\(3x + 4y = 5\)。

先找一个特解，通过观察或试值可以发现\(x = -1\)，\(y = 2\)是一个特解，即\(x_0=-1\)，\(y_0 = 2\)。

计算\((a,b)\)，这里\(a = 3\)，\(b = 4\)，\((3,4)=1\)，即\(d = 1\)。

根据通解公式，该方程的通解为\(\begin{cases}x=-1 + 4k\\y = 2-3k\end{cases}\)（\(k\in Z\)）。可以代入\(k\)的不同整数值来验证这些解都满足原方程。例如，当\(k = 1\)时，\(x = 3\)，\(y=-1\)，\(3\times3+4\times(-1)=9 - 4 = 5\)，满足原方程。

找出二元一次不定方程的一个特解方法

1. 观察法

适用情况：当方程的系数比较小且简单时，可以通过直接观察来找出特解。

示例：对于方程\(2x + 3y = 7\)，可以通过简单的尝试和观察来找到特解。当\(x = 2\)，\(y = 1\)时，\(2\times2+3\times1 = 4 + 3 = 7\)，所以\((2,1)\)是方程\(2x + 3y = 7\)的一个特解。

2. 试验法（枚举法）

适用情况：对于系数不大的方程，通过逐一尝试可能的整数取值来找到特解。一般从较小的整数开始尝试。

示例：对于方程\(3x - 4y = 1\)，

先令\(x = 1\)，则\(3\times1-4y = 1\)，解得\(y=\frac{1}{2}\)，不是整数解，舍去。

再令\(x = 3\)，则\(3\times3-4y = 1\)，解得\(y = 2\)，所以\((3,2)\)是方程\(3x - 4y = 1\)的一个特解。

3. 辗转相除法结合回代法（对于形如\(ax + by=(a,b)\)的方程）

原理：利用辗转相除法求出最大公因数\((a,b)\)的过程中进行回代，从而找到方程的特解。

步骤示例：对于方程\(111x + 321y = 3\)（先判断\((111,321)=3\)，方程有解）。

用辗转相除法求\((111,321)\)：

\(321 = 2\times111+99\)

\(111 = 1\times99 + 12\)

\(99 = 8\times12+3\)

\(12 = 4\times3\)，所以\((111,321)=3\)。

然后回代：

由\(3 = 99 - 8\times12\)，\(12 = 111 - 1\times99\)，可得\(3 = 99 - 8\times(111 - 1\times99)=9\times99 - 8\times111\)。

又因为\(99 = 321 - 2\times111\)，所以\(3 = 9\times(321 - 2\times111)-8\times111=-26\times111 + 9\times321\)，得到特解\(x=-26\)，\(y = 9\)。

4. 参数法（对于一些特殊形式的方程）

适用情况：对于形如\(y=\frac{ax + c}{b}\)（\(a\)、\(b\)、\(c\)为整数）的方程，可以通过假设\(x\)为含参数\(t\)的表达式，代入方程后使\(y\)也为整数来找到特解。

示例：对于方程\(3x - 5y = 7\)，变形为\(y=\frac{3x - 7}{5}\)。

设\(x = 4 + 5t\)（\(t\)为整数），代入\(y=\frac{3x - 7}{5}\)得\(y=\frac{3(4 + 5t)-7}{5}=\frac{12 + 15t - 7}{5}=\frac{5 + 15t}{5}=1 + 3t\)。

当\(t = 0\)时，得到特解\(x = 4\)，\(y = 1\)。

二元一次不定方程实际应用

1. 资源分配问题

问题描述：有两种不同规格的材料，一种材料每根长\(a\)米，另一种每根长\(b\)米。现在要拼接出长度为\(c\)米的材料组合，问两种材料各需要多少根？

建立方程：设长度为\(a\)米的材料需要\(x\)根，长度为\(b\)米的材料需要\(y\)根，可得到二元一次不定方程\(ax + by = c\)。

求解思路：首先判断方程是否有解，根据有解条件\((a,b)\mid c\)来确定。如果有解，通过求出特解再得到通解。例如，\(a = 3\)，\(b = 5\)，\(c = 11\)，先判断\((3,5)=1\)，\(1\mid11\)，方程有解。通过试值等方法找到特解\(x = 2\)，\(y = 1\)，通解为\(\begin{cases}x = 2 + 5k\\y = 1-3k\end{cases}\)（\(k\in Z\)）。在实际应用中，可能还需要考虑\(x\)、\(y\)为非负整数等条件来确定符合实际情况的解。比如在这个例子中，当\(k = 0\)时，\(x = 2\)，\(y = 1\)符合材料根数为非负整数的要求。

2. 购物组合问题

问题描述：在商店里，商品\(A\)单价为\(a\)元，商品\(B\)单价为\(b\)元，某人有\(c\)元钱，问购买商品\(A\)和商品\(B\)各多少件刚好把钱花完？

建立方程：设购买商品\(A\)的数量为\(x\)件，购买商品\(B\)的数量为\(y\)件，可列方程\(ax + by = c\)。

求解思路：例如，商品\(A\)单价为\(3\)元，商品\(B\)单价为\(7\)元，共有\(30\)元。方程为\(3x + 7y = 30\)。判断\((3,7)=1\)，\(1\mid30\)，方程有解。通过试值找到特解\(x = 3\)，\(y = 3\)，通解为\(\begin{cases}x = 3 + 7k\\y = 3-3k\end{cases}\)（\(k\in Z\)）。由于购买的商品数量不能是负数，所以要找到满足\(x\geq0\)且\(y\geq0\)的\(k\)的取值范围，在这里\(-\frac{3}{7}\leq k\leq1\)，\(k\)只能取整数，所以\(k = 0\)或\(k = - 1\)等，当\(k = 0\)时，\(x = 3\)，\(y = 3\)；当\(k=-1\)时，\(x=-4\)（舍去），\(y = 6\)。

3. 行程问题

问题描述：甲、乙两人分别以速度\(a\)千米/小时和\(b\)千米/小时从两地同时出发相向而行，两地相距\(c\)千米，问经过多少时间两人相遇？如果把时间设为\(x\)小时，相遇点距离甲出发地的距离设为\(y\)千米，来建立方程。

建立方程：根据路程 = 速度×时间，可得\(\begin{cases}ax + by = c\\y = ax\end{cases}\)，将\(y = ax\)代入\(ax + by = c\)，得到\(ax + b\times(ax)=c\)，化简为\((a + ab)x = c\)，这是一个关于\(x\)的一元一次方程，但如果从另一个角度看，也是一个特殊的二元一次不定方程。

求解思路：例如，甲速度为\(4\)千米/小时，乙速度为\(6\)千米/小时，两地相距\(20\)千米。方程为\(4x + 6y = 20\)，化简为\(2x + 3y = 10\)。判断\((2,3)=1\)，\(1\mid10\)，方程有解。找到特解\(x = 5\)，\(y = 0\)，通解为\(\begin{cases}x = 5+3k\\y=-2k\end{cases}\)（\(k\in Z\)）。考虑实际情况，时间\(x\)不能为负数，所以\(k\leq-\frac{5}{3}\)，同时相遇点距离甲出发地的距离\(y\)也不能为负数，所以\(k\geq0\)，综合可得\(k = 0\)，此时\(x = 5\)，\(y = 0\)符合两人在甲出发地相遇的情况。

4. 工程合作问题

问题描述：有甲、乙两个工程队，甲队单独完成一项工程需要\(a\)天，乙队单独完成需要\(b\)天，现在两队合作完成一项工程，设合作的天数为\(x\)，甲队完成的工作量占总工作量的比例为\(y\)，总工作量设为\(1\)，建立方程。

建立方程：甲队一天完成的工作量为\(\frac{1}{a}\)，乙队一天完成的工作量为\(\frac{1}{b}\)，可得\(\begin{cases}x(\frac{1}{a}+\frac{1}{b})=1\\y=\frac{x}{a}\end{cases}\)，将\(y=\frac{x}{a}\)代入第一个方程并化简得到\((\frac{1}{a}+\frac{1}{b})y + \frac{1}{b}(1 - y)=1\)，这也是一个二元一次不定方程。

求解思路：例如，甲队单独完成需要\(3\)天，乙队单独完成需要\(4\)天。方程为\((\frac{1}{3}+\frac{1}{4})x = 1\)，化简为\(\frac{7}{12}x = 1\)，从二元一次不定方程角度看类似\(7x - 12y = 0\)（设\(y = 1 - x\)）。\((7,12)=1\)，\(1\mid0\)，方程有解。特解为\(x = 0\)，\(y = 0\)，通解为\(\begin{cases}x = 12k\\y = 7k\end{cases}\)（\(k\in Z\)）。在实际工程问题中，\(x\)表示工作天数，\(k = 0\)时符合工程还未开始的情况，\(k = 1\)时，\(x = 12\)，\(y = 7\)，表示经过12天甲队完成工作量的比例为\(\frac{7}{12}\)。

数论基础 - 主要研究整数性质以及和它有关的规律