为什么大小不超过2n的n+1个不同的自然数中必有两个数是互素的

这个问题用肯定的语句来说，就是：小于或者等于2n的n+1个不同的自然数之中，一定有两个数是互素的。互素，也就是互质。两个数互素，就是它们的公约数只有1（不考虑负的公约数）。

关于这个问题的来历，有一则很动人的小故事。

1962年，匈牙利数学家路易斯·波萨刚满15岁。就在这一年，他发表了一篇论文，提出了一条判定一个图是哈密顿图的新定理。这条定理至今还被写在一些给高年级大学生、研究生们阅读的图论书里，在国际上是很出名的。

发现小波萨的“伯乐”是匈牙利科学院院士、数学家保尔·爱尔特希。他是目前世界上最多产的数学家之一，经常到世界各地进行学术访问与交流，也是我国《数学研究与评论》杂志的一位学术顾问。那是在1959年的夏天，爱尔特希刚从美国讲学回到匈牙利，听说小男孩波萨在数学上很聪明，有心试他一试。当时小波萨还不到12岁。

第二天，爱尔特希和小波萨一起用餐，在波萨喝着汤的时候，就向他提了一个数学问题：为什么大小不超过2n的n+1个不同的自然数中，必有两个数是互素的？

小波萨像大人那样坐在那里不慌不忙地喝着汤，同时思索着爱尔特希刚才向他提出的问题。只过了半分钟左右，他就回答说：“因为大小不超过2n的n+1个自然数中，一定有两个相邻的数，而这两个相邻的数是互素的。”就这样，小波萨正确、简明地回答了大数学家爱尔特希的问题。

为什么大小不超过2n的n+1个不同的自然数中，一定会有两个相邻的数呢？这是因为在一个由自然数组成的集合中，要求其中所有的元素都小于或者等于2n，而且没有任何两个数是相邻的，符合这种条件的自然数集合，其中元素的个数顶多是n。这就是自然数集合｛1，3，5，7，…，2n-l｝以及｛2，4，6，8，…，2n｝，n+1大于n，所以不超过2n的n+1个自然数中，当然一定会有两个是相邻的数了。

又为什么相邻的两个自然数，一定是互素的呢？不妨将其中一个数记为k，另—个数记为k+1。要证明它们是互素的，只要证明它们只有公约数1。因为k是一个抽象的数，不能说它具体地等于几，所以不能采用分解质因数的办法求出k和k+1的最大公约数。但我们可以采用辗转相除法求它们的最大公约数：用k去除k+1时余数是1，所以k与k+1的最大公约数是1。如果你对辗转和除法不是很熟悉的话，也不要紧。先设d是它们的公约数，那么根据公约数的定义，$\frac{k}{d}$与$\frac{{k + 1}}{d}$都是自然数。所以

$\frac{{k + 1}}{d} - \frac{k}{d} = \frac{1}{d}$

是自然数。由此可以看出：d只能等于1。这也就是说，在正整数范围内，唯有1才够资格作为相邻两数的公约数。这就证明了相邻两数是互素的。

爱尔特希是位饮誉世界的数学家，当然很明白小波萨的意思，以上两点补充说明，毋须再向他作任何解释。爱尔特希对小波萨的回答极为赏识，给予了很高的评价，认为这件事足可以与高斯10岁时，用巧妙方法算出从1到100的所有正整数的和相媲美。