求gcd(2016!+1,2015!+1)的方法咨询：已尝试辗转相减无进展

嘿，这个问题其实可以用欧几里得算法一步步拆解，你已经想到用 gcd(a,b)=gcd(a,b−a) 了，咱们顺着这个思路走下去就好：

设 ( a = 2016! + 1 )，( b = 2015! + 1 )，根据欧几里得算法核心公式：
gcd(a, b) = gcd(b, a - b)

先计算 ( a - b ) 的值：
( 2016! + 1 - (2015! + 1) = 2016×2015! - 2015! = 2015!×(2016 - 1) = 2015!×2015 )

现在问题就转化为求：
gcd(2015! + 1, 2015!×2015)

根据gcd的性质，我们可以把这个复合的gcd拆成两个独立部分分析：
gcd(m, n×k) = gcd(m, n) × gcd(m, k)（当n和k互质时成立，这里2015!和2015存在公因数，但我们可以分开看）

首先看 gcd(2015! + 1, 2015!)：
这两个数是相邻的整数（2015! 和 2015!+1），相邻整数必然互质，所以这个gcd的结果是1。

那现在整体的gcd就等于剩下的部分：gcd(2015! + 1, 2015)

先把2015分解质因数：2015 = 5 × 13 × 31，这三个都是质数。

对于任意质数 ( p ≤ 2015 )，( p ) 是2015!的因数（因为2015!是1到2015所有整数的乘积），所以：
( 2015! ≡ 0 \pmod{p} )
那么 ( 2015! + 1 ≡ 0 + 1 ≡ 1 \pmod{p} )

也就是说，2015!+1除以5、13、31的余数都是1，而1和任何数的gcd都是1，所以：

• gcd(2015! + 1, 5) = 1
• gcd(2015! + 1, 13) = 1
• gcd(2015! + 1, 31) = 1

因为5、13、31互质，所以 gcd(2015! + 1, 2015) = 1×1×1 = 1

把所有步骤串起来，我们得到：
gcd(2016! + 1, 2015! + 1) = 1

内容的提问来源于stack exchange，提问作者Dragon Surfer