如何证明对每个n∈ℕ，gcd(3ⁿ+5ⁿ⁺¹,3ⁿ⁺¹+5ⁿ)=2或14？

嗨，我来帮你搞定这个问题！其实不用纠结归纳法的瓶颈，直接用最大公约数的核心性质来推导会更顺畅，咱们一步步拆解：

第一步：利用gcd的基本性质简化表达式 #

回忆最大公约数的关键性质：对于整数a、b和整数k，有gcd(a, b) = gcd(b, a - k*b)。这个性质能帮我们消掉高次幂，简化计算。

设a = 3ⁿ + 5ⁿ⁺¹，b = 3ⁿ⁺¹ + 5ⁿ，我们选择k=5来构造线性组合：

a - 5*b = (3ⁿ + 5ⁿ⁺¹) - 5*(3ⁿ⁺¹ + 5ⁿ)
         = 3ⁿ + 5*5ⁿ - 15*3ⁿ - 5*5ⁿ
         = -14*3ⁿ

根据gcd性质，gcd(a, b) = gcd(b, a - 5*b) = gcd(3ⁿ⁺¹ + 5ⁿ, 14*3ⁿ)

第二步：进一步简化gcd表达式 #

接下来看3ⁿ和3ⁿ⁺¹ + 5ⁿ的最大公约数：
gcd(3ⁿ, 3ⁿ⁺¹ + 5ⁿ) = gcd(3ⁿ, 5ⁿ)（因为gcd(x, x*c + y)=gcd(x,y)）
由于3和5互质，所以gcd(3ⁿ,5ⁿ)=1。

根据gcd的另一个性质：如果gcd(x,y)=1，那么gcd(x, m*y)=gcd(x,m)。这里x=3ⁿ⁺¹+5ⁿ，y=3ⁿ，m=14，所以：
gcd(3ⁿ⁺¹ + 5ⁿ, 14*3ⁿ) = gcd(3ⁿ⁺¹ + 5ⁿ, 14)

第三步：分析gcd(3ⁿ⁺¹ + 5ⁿ,14)的可能值 #

14的正因数是1、2、7、14，我们逐一分析：

• 必能被2整除：3ⁿ⁺¹是奇数，5ⁿ也是奇数，奇数+奇数=偶数，所以3ⁿ⁺¹+5ⁿ是偶数，2一定是公约数。
• 是否能被7整除：计算3ⁿ⁺¹ + 5ⁿ mod 7：
  • 3的幂模7的周期是6：3¹≡3, 3²≡2, 3³≡6, 3⁴≡4, 3⁵≡5, 3⁶≡1
  • 5的幂模7的周期是6：5¹≡5, 5²≡4, 5³≡6, 5⁴≡2, 5⁵≡3, 5⁶≡1
  • 代入可得：当且仅当n ≡1 mod 3时，3ⁿ⁺¹ +5ⁿ ≡0 mod7（比如n=1时，3²+5=14≡0；n=4时，3⁵+5⁴=243+625=868，868÷7=124）

结论 #

• 当n ≡1 mod3时，gcd(3ⁿ⁺¹ +5ⁿ,14)=14，因此原式的gcd为14；
• 其他情况，gcd(3ⁿ⁺¹ +5ⁿ,14)=2，因此原式的gcd为2。

这样就证明了对所有n∈ℕ，gcd的值只能是2或14啦～

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