整数最大公约数问题

发布网友 发布时间：2024-07-29 20:01

我来回答

共3个回答

热心网友 时间：2024-08-06 18:02

最大公约数是120.

n^5-5n^3+4n = n(n²-1)(n²-4) = (n-2)(n-1)n(n+1)(n+2),
由n > 2, 即知其为五个相邻正整数之积.
当n = 3时, 值为5! = 120.
只需证明五个相邻正整数的乘积一定被5! = 120整除,
就能说明所有这样的数的最大公约数是120.

如果学过组合数, 这个结论可以很简单的证明:
n中选5的组合数C(n,5) = n(n-1)(n-2)(n-3)(n-4)/5!,
组合数总是整数, 因此5!一定整除分子n(n-1)(n-2)(n-3)(n-4),
对任意n ≥ 5都成立.

如果没学过组合数, 可以分别证明:
五个相邻整数的乘积一定被8, 3和5整除,
这样可以就推出一定被120整除.
(1) 五个相邻整数中至少有两个偶数,
两个相邻偶数中至少有一个是4的倍数,
一个偶数与一个4的倍数的乘积必然是8的倍数,
从而五个相邻整数之积一定被8整除.
(2) 五个相邻整数中至少有一个是3的倍数,
从而五个相邻整数之积一定被3整除.
(3) 五个相邻整数中至少有一个是5的倍数,
从而五个相邻整数之积一定被5整除.
综合即得五个相邻整数的乘积一定被120整除.

一般的, k个相邻整数的乘积一定被k!整除.
组合数的证明仍然适用, 但后面那种讨论的方法要替换为更一般的理论.
这属于"阶乘的标准分解式"这一知识点.
详细的就不说了.

热心网友 时间：2024-08-06 17:55

热心网友 时间：2024-08-06 17:59

在“求两个正整数的最大公约数”问题的算法的问题解决中，除了辗转相除求最大公约数和更相减损之术，是否还有其它的算法。 5标签: 求两个正整数的最大公约数, 两个 公约数, 公约数在“求两个正整数的最大公约数”问题的算法的问题解决中，除了辗转相除求最大公约数和更相减损之术，是否还有其它的算法。辗转相除求最大公约数：假设求两个正整数m和n的最大公约数。以下是辗转的算法：分别用m,n,r表示被除数、除数、余数①若m<n，则交换m和n 的值②求m除以n的余数r.③若r=0,则n为最大公约数.，结束。若r≠0,执行第③步.④将n的值放在m中,将r的值放在n中.⑤返回重新执行第②步。更相减损之术求最大公约数的本质是将辗转相除变为辗转相减。假设求两个正整数m和n的最大公约数。以下是更相减损之术的算法：分别用m,n,r表示被减数、减数、差①若m<n，则交换m和n 的值②求m减去n的差值r.③若r=0,则n为最大公约数.，结束。若r≠0,执行第④步.④若r<n，则令m=n,n=r。否则m=r，n的值不变。⑤返回重新执行第②步。
以上回答你满意么？