关于任意n∈N时5n+3与7n+4互素及s、t非唯一性的求证方法咨询

一、证明互素（欧几里得算法） #

咱们用最经典的欧几里得算法来算它们的最大公约数，一步步推就很清楚：

• 首先计算 gcd(7n+4, 5n+3)，根据欧几里得算法规则 gcd(a,b)=gcd(b,a mod b)：
  1. 7n+4 = 1*(5n+3) + (2n+1)，所以 gcd(7n+4,5n+3) = gcd(5n+3,2n+1)
  2. 5n+3 = 2*(2n+1) + (n+1)，所以 gcd(5n+3,2n+1) = gcd(2n+1,n+1)
  3. 2n+1 = 1*(n+1) + n，所以 gcd(2n+1,n+1) = gcd(n+1,n)
  4. n+1 = 1*n + 1，所以 gcd(n+1,n) = gcd(n,1) = 1
• 最终最大公约数是1，说明对于任意自然数n，5n+3与7n+4互素。

二、s、t的非唯一性及通用计算方法 #

你已经找到一组解 s=7、t=-5，代入验证确实满足 7*(5n+3) + (-5)*(7n+4) = 1。其实这类线性不定方程的解是无穷多的，不用靠猜，咱们可以基于已知解生成所有解：

假设 (s₀,t₀) 是一组满足 s*(5n+3) + t*(7n+4) = 1 的解，那么所有解可以表示为：

s = s₀ + k*(7n+4)
t = t₀ - k*(5n+3)

其中 k 是任意整数（正整数、负整数、0都可以）。

验证通解的正确性： #

把s和t代入方程展开看看：

(s₀ + k*(7n+4))*(5n+3) + (t₀ - k*(5n+3))*(7n+4)
= s₀*(5n+3) + t₀*(7n+4) + k*(7n+4)(5n+3) - k*(5n+3)(7n+4)
= 1 + 0 = 1

完全成立！举个例子，取k=1：

• s = 7 + (7n+4) = 7n+11
• t = -5 - (5n+3) = -5n-8
  代入验证：(7n+11)(5n+3) + (-5n-8)(7n+4) = 35n²+21n+55n+33 -35n²-20n-56n-32 = 1，完全符合要求。

随便选个整数k，就能得到一组新的s和t，这就证明了解的非唯一性啦～

内容的提问来源于stack exchange，提问作者Amelia O'Leary