二元一次不定方程

基础

• $ax+by=c$
  $$\begin{gathered} 1.c=0 \\ (a,b)=d,\frac{ax+by}{d}=>a^{\prime }x+b^{\prime }y=0,(a^{\prime },b^{\prime })=1 \\ x=-\frac{by}{a},a|y,y=at \\ 2.x=-\frac{bat}{a}=-bt \\ x=-bt,y=at,(t=0,\pm 1,\pm 2,.....) \\ 2.c\ne 0,c是一个负整数 \\ (a,b)=d,\frac{ax+by}{d}=\frac{c}{d}=>a^{\prime }x+b^{\prime }y=c^{\prime },(a^{\prime },b^{\prime })=1,d|c才有整数解,c^{\prime }才是整数。 \end{gathered}$$

$$(a,b)=1=>一定有ax+by=1,x,y\in Z$$
4.
$$(a,b)=1,a,b为正整数，c是一个整数=>一定有ax+by=c$$
5.$ax+by=c为二元一次不定方程$
$$\begin{gathered} a,b,c都是正整数，(a,b)=1，有一组整数解x=x_0,y=y_0 \\ 则ax+by=c的一切整数解可表示为： \\ x=x_0-bt,y=y_0+at \\ 其中，t=0,\pm 1,\pm 2,... \\ a(x_0-bt)+b(y_0+at)=a{x}_0+b{y}_0=c \end{gathered}$$
6.$$\begin{gathered} 39x+19y=1,求x和y \\ (19,39)=1,39=19\times 2+1 \\ 1=39-19\times 2 \\ x=1,y=-2 \end{gathered}$$
7.$39x+20y=1$
$$\begin{gathered} (20,39)=1,39=20\ast 1+19 \\ 20=19\ast 1+1 \\ 1=20-19=20-(39-20)=2\times 20-39 \\ x=-1,y=2 \end{gathered}$$
8.$133x+43y=1$
$$\begin{gathered} (133,43)=1,133=43\ast 3+4,43=4\ast 10+3 \\ 4=3+1,3=1+2 \\ 1=4-3=(133-43\times 3)-(43-4\times 10) \\ =133-43\times 4+4\times 10 \\ 133-43\times 2+(133-43\times 3)\times 10=133-43\times 4+133\times 10-43\times 30 \\ =133\times 11-43\times 34 \\ x=11,y=-34 \end{gathered}$$
9. $79x+123y=31$

function extended_gcd(a, b)if b == 0return a, 1, 0  # 返回gcd(a, b), x, yelsegcd, x1, y1 = extended_gcd(b, a % b)x,y = y1, x1 - Int(floor(a // b)) * y1return gcd, x, yend
endgcd, x, y = extended_gcd(79, 123)
println("gcd = $gcd, x = $x, y = $y")

gcd = 1, x = -14, y = 9

$$\begin{gathered} s=-14,t=9,79\times (-14)+123\times 9=1 \\ x=31s=31\times (-14)=-434,y=31t=31\times 9=279 \\ 31\times (79x+123y)=31 \\ x=-434,y=279是一组整数解，一切整数解可表示如下： \\ x=x_0-bt=-434-123t \\ y=y_0+at=279+79t \\ t=0,\pm 1,\pm 2,... \end{gathered}$$

理论

下面内容来自文心一言的自动生成

二元一次不定方程

在数学中，二元一次不定方程是指含有两个未知数，且未知数的次数都是1的整系数方程，其解集不是由有限个解组成的，而是有无限多个解。这类方程的一般形式可以表示为：

$$ax+by=c$$

其中 $a,b,c$ 是整数，且 $a$ 和 $b$ 不同时为0。

解法概述

解二元一次不定方程的基本思路是通过某种方式消去一个未知数，从而得到一个关于另一个未知数的方程，这个方程可能是一个一元一次方程，也可能仍然是不定的。然后，通过求解这个一元方程（如果可能的话），找到未知数的解集。

具体步骤

1. 化简方程：首先，尝试通过乘以某个整数来消去方程中的分数或小数，使得方程变为整系数方程。

2. 求解一个未知数：

   • 如果 $b\ne 0$，可以将方程 $ax+by=c$ 改写为 $x=\frac{c-by}{a}$。
   • 这样，对于 $y$ 的每一个整数值，都可以求出 $x$ 的一个对应整数值（如果 $a$ 能整除 $c-by$ 的话）。

3. 找出特解：

   • 通过尝试或利用其他条件（如 $x,y$ 的取值范围、最大公约数等），找出一组特解 $(x_0,y_0)$，即满足原方程的一组整数解。

4. 找出通解：

   • 利用特解和方程的性质，找出所有整数解的通解形式。
   • 通常，如果 $d=\gcd (a,b)$（$a$ 和 $b$ 的最大公约数），那么方程 $ax+by=c$ 有整数解当且仅当 $d\mid c$（$d$ 能整除 $c$）。
   • 在这种情况下，可以设 $a=d{a}_1,b=d{b}_1,c=d{c}_1$，其中 $a_1,b_1,c_1$ 是整数，且 $\gcd (a_1,b_1)=1$。
   • 方程 $ax+by=c$ 可以改写为 $a_{1}x+b_{1}y=c_1$。
   • 利用扩展欧几里得算法找到 $a_1{x}_1+b_1{y}_1=1$ 的一组解 $(x_1,y_1)$。
   • 那么，方程 $a_{1}x+b_{1}y=c_1$ 的通解可以表示为 $(x,y)=(c_1{x}_1+k{b}_1,c_1{y}_1-k{a}_1)$，其中 $k$ 是任意整数。
   • 将 $a_1,b_1,c_1$ 替换回 $a,b,c$，即可得到原方程的通解。

示例

解方程 $3x+5y=16$。

• 首先，观察方程，发现 $a=3,b=5,c=16$，且 $\gcd (3,5)=1$，所以 $d=1$ 能整除 $c$，方程有解。
• 但为了更直观地展示过程，我们可以直接尝试找特解。例如，当 $y=2$ 时，$x=\frac{16-5\times 2}{3}=2$，得到一组特解 $(x_0,y_0)=(2,2)$。
• 接下来找通解。由于 $\gcd (3,5)=1$，我们可以直接利用特解和方程形式写出通解。但在这里，为了说明过程，我们可以考虑另一种方式：利用扩展欧几里得算法找到 $3x+5y=1$ 的一组解（虽然这里 $c=1$，但方法相同）。假设找到的一组解是 $(x_1,y_1)=(2,-1)$（注意这不是唯一解，但足以说明问题）。
• 那么，方程 $3x+5y=16$ 的通解可以表示为 $(x,y)=(16\times 2+5k,16\times (-1)-3k)=(32-3k,-16+5k)$，其中 $k$ 是任意整数。

不定方程

勾股

• $x^2+y^2=z^2$该不定方程的解为正整数，称为勾股数
  $$\begin{gathered} 该方程的适合条件:x>0,y>0,z>0,(x,y)=1，2|x \\ 解：x=2ab,y=a^2-b^2,z=a^2+b^2 \\ a,b都是正整数 \end{gathered}$$
• 求一组勾股数
  $设a=7,b=3,z=7^2+3^2=58,x=2\times 7\times 3=42,y=7^2-3^2=40$

求不定方程$4x-9y+5z=8$

$$\begin{gathered} 1.\alpha =8-5z,a+5z=8 \\ 4x-9y=\alpha ,\alpha \in Z \\ 2.4s+9t=1,(4,9)=1 \\ (1)9=4\times 2+1,1=4\times (-2)+9 \\ (2)s=-2,t=1 \\ 3.4x-9y=\alpha =\alpha (4s+9t)=4\alpha s+9\alpha t \\ (1)x=\alpha s=-2\alpha ,y=-\alpha t=-\alpha \\ (2)x=x_0-b\beta =-2\alpha +9\beta \\ y=y_0+\alpha \beta =-\alpha +4\beta \\ \beta =0,\pm 1,\pm 2,.... \\ 4.z=1,\alpha =3,\alpha +5z=8 \\ \alpha =3-5c \\ z=1+c \\ c=0,\pm 1,\pm 2,.... \\ 5.\alpha =3-5c \\ (1)x=-2\alpha +9\beta =-6+10c+9\beta \\ (2)y=-\alpha +4\beta =-3+5c+4\beta \\ z=1+c \\ c,\beta \in Z \end{gathered}$$

$xy=x^2+6$的整数解

$$\begin{gathered} 1.x(y-x)=6 \\ x|(-6) \\ 2.x=1,y=7 \\ x=-1,y=-7 \\ x=2,y=5 \\ x=-2,y=-5 \\ x=3,y=5 \\ x=-3,y=-5 \\ x=6,y=7 \\ x=-6,y=-7 \end{gathered}$$

费马大定理

以下内容由文心一言自动生成
费马大定理（Fermat’s Last Theorem），又被称为“费马最后的定理”，是由17世纪法国数学家皮耶·德·费马（Pierre
de Fermat）提出的一个著名数学猜想。该定理的概要为：当整数n > 2时，关于x, y, z的方程x^n + y^n =
z^n没有正整数解。

历史背景

• 提出：费马大定理最初出现在费马的《页边笔记》中，他断言该定理成立但并未给出证明，只是表明他已找到一个绝妙的证明而页边没有足够的空位写下。
• 探索与猜想：费马去世后，他的猜想激发了众多数学家的兴趣，许多数学家尝试证明或反驳这一猜想，但均未果。
• 奖金激励：德国人沃尔夫斯凯尔（Paul Wolfskehl）曾宣布以10万马克作为奖金，奖给在他逝世后一百年内第一个证明该定理的人，这进一步激发了数学界对费马大定理的研究热情。

证明过程

• 早期进展：在费马提出猜想后的几个世纪里，数学家们逐步证明了n为某些特定值（如3、4、5等）时定理成立。
• 关键突破：1995年，英国数学家安德鲁·怀尔斯（Andrew Wiles）宣布他证明了费马大定理。怀尔斯的证明基于椭圆曲线和模形式的深刻理论，特别是他利用谷山-志村猜想（后由怀尔斯和他的学生理查·泰勒共同证明）作为关键工具。
• 证明认可：怀尔斯的证明经过严格的审查后被广泛接受，费马大定理终于从猜想变成了定理。

影响与意义

• 数学发展：费马大定理的证明过程推动了数学多个分支的发展，包括代数几何、数论等。
• 科学精神：怀尔斯长达七年的证明过程体现了数学家们坚韧不拔的科学精神和对真理的不懈追求。
• 历史地位：费马大定理作为数学史上最著名的猜想之一，其证明过程被载入史册，成为数学界的一个传奇。

综上所述，费马大定理是一个具有深厚历史背景和重要科学意义的数学定理，它的证明不仅解决了困扰数学家们三百多年的难题，也推动了数学的发展和进步。

同余

基础

• $a,b是整数，m是一个固定的正整数，当m|(a-b)（即m能整除a-b）时,称a、b对模m同余，记作a\equiv b(modm),否则a\not\equiv b(modm)$
  $比如：32\equiv 12(mod4),4|(32-12)$
• $a\equiv a(modm)$
• $$\begin{gathered} a\equiv b(modm)=>b\equiv a(modm)， \\ （这个显然，同余关系构成剩余类，构成等价关系，但这是抽象代数，不属于初等数论） \end{gathered}$$
• $a\equiv b(modm)=>a-b=mt,t\in Z$
• $a\equiv b(modm),c\equiv d(modm)=>a+c\equiv b+d(modm)$
• $a\equiv b(modm),c\equiv d(modm)=>a-c\equiv b-d(modm)$
• $a\equiv b(modm)=>ac\equiv bc(modm)$
• $a\equiv b(modm),c\equiv d(modm)=>ac\equiv bd(modm)$
• $a\equiv b(modm)=>a^n\equiv b^n(modm)$
• $$\begin{gathered} 如果a_1,a_2，...,b_1,b_2,...,b_n都是正整数，而m,n都是正整数，则当 \\ {a}_1\equiv b_1(modm) \\ {a}_2\equiv b_2(modm) \\ ... \\ {a}_n\equiv b_n(modm) \\ 则a_1+a_2+...+a_n\equiv b_1+b_2+...+b_n(modm) \end{gathered}$$
• 例：5781308能被9整除吗？
  $$\begin{gathered} 1. \\ 5\times 10^6+7\times 10^5+8\times 10^4+1\times 10^3+3\times 10^2+0\times 10^1+8 \\ 10mod9=1,10^n\equiv 1(mod9),10^6\equiv 1(mod9),5\times 10^6\equiv 5\times 1(mod9) \\ 5781308=5+7+8+1+3+0+8=32 \\ 9\nmid 32 \\ 5781308不能被9整除 \\ 2.能被7整除吗 \\ 10mod7=3,10^n\equiv 3(mod7),10^6\equiv 3(mod7),5\times 10^6\equiv 5\times 3(mod7) \\ 5781308=5\ast 3+7\ast 3+8\ast 3+1\ast 3+3\ast 3+0\ast 3+8\ast 3=96,7\nmid 96 \\ 5781308不能被7整除 \\ 3.能被4整除吗 \\ 10mod4=2,10^n\equiv 2(mod4),10^6\equiv 2(mod4),5\times 10^6\equiv 5\times 2(mod4) \\ 5781308=5\ast 2+7\ast 2+8\ast 2+1\ast 2+3\ast 2+0\ast 2+8\ast 2=64,4\mid 64 \\ 5781308能被4整除 \end{gathered}$$
• 例： 7742238能被6整数吗？
  $$\begin{gathered} 1. \\ 7\times 10^6+7\times 10^5+4\times 10^4+2\times 10^3+2\times 10^2+3\times 10^1+8 \\ 10mod6=4,10^n\equiv 4(mod6),10^6\equiv 4(mod6),7\times 10^6\equiv 7\times 4(mod9) \\ 7742238=7\ast 4+7\ast 4+4\ast 4+2\ast 4+2\ast 4+3\ast 4+8\ast 4=132 \\ 6\mid 132 \\ 5781308能被6整除 \end{gathered}$$
• 弃九法
  $$\begin{gathered} a=a_{n}10^n+a_{n-1}10^{n-1}+...+a_0 \\ b=b_{n}10^n+b_{n-1}10^{n-1}+...+b_0 \\ ab=P \\ P=c_{l}10^l+c_{l-1}10^{l-1}+...+c_0 \\ a\equiv a_n+a_{n-1}+...+a_0(mod9) \\ b\equiv b_m+b_{m-1}+...+b_0(mod9) \\ P\equiv c_l+c_{l-1}+...+c_0(mod9) \\ (a_n+a_{n-1}+...+a_0)(b_m+b_{m-1}+...+b_0)\equiv c_l+c_{l-1}+...+c_0(mod9) \\ 特别注意，上面这个式子不成立，则ab\ne P \\ 但上面式子如果成立，不能说ab=P \end{gathered}$$
• $2431\ast 92=93452?$
  $$\begin{gathered} 2431=2+4+3+1=10\equiv 1(mod9) \\ 92=9+2=11\equiv 2（mod9) \\ 93452=9+3+4+5+2=23\equiv 5(mod9) \\ 1\times 2=2\not\equiv 5(mod9) \\ 所以上面等式不成立。 \end{gathered}$$

参考文献

1.文心一言
2.《初等数论》陈景润