我最近卡在一个最大公约数（GCD）的问题上，问题是求当$a>0$时$\gcd(5a+3,4a+7)$的值。我已经折腾好久了，遇到了不少问题，具体情况如下：

我的尝试过程 #

1. 欧几里得算法的困惑
   我一开始尝试用欧几里得算法，但不知道怎么处理变量$a$来计算余数——把这两个式子当作关于$a$的多项式来做除法，感觉完全摸不着头绪。

2. 互质性的尝试失败
   试了几个$a$值后，我一度以为它们是互质的，就试着找整数$x$和$y$，让$x(5a+3) + y(4a+7) = 1$。整理这个式子后得到：
   $$a(5x+4y)+(3x+7y) = 1$$
   这就要求$5x+4y=0$且$3x+7y=1$，但解这个方程组会发现没有整数解，所以互质的思路不成立。

3. 归纳法的碰壁
   之后我又尝试用归纳法证明，结果也行不通。特别是我不知道怎么推导类似“如果$d|(5a+8)$那么$d|(5a+3)$”的结论，没法通过这种方式得到矛盾。

4. 大量试值后的猜想
   无奈之下我又试了更多$a$值，检查到前2000个正整数后，发现GCD的可能取值只有两个：

• 当$a$是$27+23j$（$j$为非负整数）的形式时，两者的最大公约数是23；
• 比如$a=4$时，$5×4+3=23$，$4×4+7=23$，GCD就是23；
• 其他情况下，两者都是互质的（GCD=1）。

已完成的证明 #

我已经能证明当$a=27+23j$时，GCD是23，用欧几里得算法的步骤如下：

$5(27+23j) +3 = [4(27+23j)+7] + 23+23j$
$4(27+23j)+7 = (23+23j)×4 + 23$
$(23+23j)×4 = 23(4+4j) + 0$

由此可得：
$$\gcd(5(27+23j)+3,4(27+23j)+7) = \gcd(23(4j+4),23) = 23$$
这个结论对任意非负整数$j$都成立。

我的核心困惑 #

现在我卡壳的地方是：怎么证明当$a$不是4，也不是$27+23j$的形式时，$\gcd(5a+3,4a+7)=1$？ 我不知道该怎么约束$a$来推进这个证明，希望能得到相关的技巧指导。

另外要说明，这个问题和之前类似的提问有两点不同：一是我们讨论的多项式不一样；二是我的核心需求不是给定$a$的条件求GCD，而是反过来证明当$a$不满足某些条件时GCD必为1。我对自己的猜想很有信心，但急需合适的方法来完成证明。

备注：内容来源于stack exchange，提问作者Mani