证明在前2n个自然数中任意取出n+1个数,其中必有2个数互质.用抽屉原理.
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/23 06:44:09
证明在前2n个自然数中任意取出n+1个数,其中必有2个数互质.用抽屉原理.
证明在前2n个自然数中任意取出n+1个数,其中必有2个数互质.用抽屉原理.
证明在前2n个自然数中任意取出n+1个数,其中必有2个数互质.用抽屉原理.
把前2n个自然数1,2,3,4,5,6,……,2n-1,2n
分成n个组:(1,2)、(3,4)、(5,6)、……,(2n-1,2n)
在前2n个自然数(n组)中任意取出n+1个数,其中必有2个数属于同一个组,
也就是必有2个数是相邻自然数
因为两个相邻自然数的最大公约数是1
所以在前2n个自然数中任意取出n+1个数,其中必有2个数互质.
2N个数至少有N个数是2的倍数。如果取N+1个数至少有一个不是2的倍数。假设
N+1个数都不互质。即其中任两个数都有公因数1以外的质因数,因为N+1中至少有两个数是连续数。一个是质数一个是偶数,这两个数不可能有相同的质因数。所以这两个数肯定互质。...
全部展开
2N个数至少有N个数是2的倍数。如果取N+1个数至少有一个不是2的倍数。假设
N+1个数都不互质。即其中任两个数都有公因数1以外的质因数,因为N+1中至少有两个数是连续数。一个是质数一个是偶数,这两个数不可能有相同的质因数。所以这两个数肯定互质。
收起
首先,有一个道理是n和n+1是互质的不用证明了吧?想一下,能整除n的数去除n+1结果肯定会余1的.
然后问题就简单了,从2n个数里取n+1个数必须有两个数是挨着的。就用传说中的抽屉原理,数只分为奇数和偶数,那么选出来的所有数都不挨着只能全是奇数或偶数,但是2n个数里面一共才有n个奇数或者偶数,即使所有的奇数都选上了,那么剩下的那个必然是偶数所以会出现两个挨着数,他们是互质的。
我说...
全部展开
首先,有一个道理是n和n+1是互质的不用证明了吧?想一下,能整除n的数去除n+1结果肯定会余1的.
然后问题就简单了,从2n个数里取n+1个数必须有两个数是挨着的。就用传说中的抽屉原理,数只分为奇数和偶数,那么选出来的所有数都不挨着只能全是奇数或偶数,但是2n个数里面一共才有n个奇数或者偶数,即使所有的奇数都选上了,那么剩下的那个必然是偶数所以会出现两个挨着数,他们是互质的。
我说明白了没?
收起