设 m 是自然数，a=m^2+4 ，b=(m+1)^2+4 ，求 a 与 b 的最大公约数的最大值

cloudater

一个数论题目

各位好，我又来了。我水平不行，只能发帖问。

我家小朋友数论水平不大好。遇见这题，不知道怎么解答：

设：
设m是自然数
\(a=m^2+4\)
\(b=(m+1)^2+4\)

那么a与b的最大公约的最大值。

请问这题怎么做呢？

我本来想法是两个连续自然数的平方，各加4。可以被一个相同的质数分解。

cloudater

不过，这个是选择题。可以选5、7、17、19。我家小朋友说，6分钟一题，要么丢进去死算也来得及

不过，肯定想知道怎么来解这题。

Treenewbee

\[(a,b)=(a,b-a)=(m^2+4,2m+1)\]
\[m=2k,(a,b)=(4k^2+4,4k+1)=(-k+4,4k+1)=(17,4k+1)<=17\]
\[m=2k+1,(a,b)=(4k^2+4k+5,4k+3)=(4k-4,4k+3)=(7,4k+3)<=7\]

Treenewbee

辗转相除法，m=8时取最大值17

cloudater

感谢老师答疑解惑，顺便查了一下辗转相除法。

辗转相除法，也称为欧几里德算法，是用于计算两个正整数的最大公约数（最大公因数）的一种算法。它基于以下原理：如果两个数 p 和 q 满足 p > q，则它们的最大公约数等于 q 和 p mod q（p 除以 q 的余数）的最大公约数。

辗转相除法的步骤如下：

将两个数 p 和 q 进行相除，得到余数 r。
如果 r 等于 0，则 q 即为最大公约数。
如果 r 不等于 0，则将原来的 q 赋值给 p，将 r 赋值给 q，然后重复步骤 1。
这个过程一直持续到余数为 0 为止。最后的 q 即为最大公约数。

辗转相除法是一种非常高效的计算最大公约数的方法，也被广泛应用于计算机科学和数学领域。