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

1959年夏天，保尔·爱尔特希用“为什么大小不超过2n的n+1个不同的自然数中必有两个数是互素的”这一道题，来考当时年仅12岁的匈牙利数学家路易斯·波萨。保尔·爱尔特希是匈牙利的科学院院士，是世界上最多产的数学家之一，也曾是我国《数学研究与评论》杂志的一位学术顾问。当时，小波萨仅思索了半分钟左右就答出来了，令爱尔特希极为赏识。

小波萨的回答是这样的：因为大小不超过2n的n+1个自然数中，一定有两个相邻的数，而这两个相邻的数是互素的。

我们很容易知道两个相邻自然数一定互素：如果p是这两个相邻数的公约数，那么p一定是它们的差1的公约数，从而p=1。但是，为什么大小不超过2n的n+1个不同的自然数中，一定会有两个相邻的数呢?这是因为在一个由自然数组成的集合中，要求其中所有的元素都小于或者等于2n，而且没有任何两个数是相邻的，符合这种条件的自然数集合，其中元素的个数顶多是n个。这就是自然数集合{1，3，5，…，2n-1}或{2，4，6，…，2n}。在这一集合中如果再要加入一个数，即有n+1个数，那么必然会有两个数是相邻的。

波萨在他15岁那年，又一次显现了他卓越的数学才华。他发表了一篇论文，提出了一个判定一个图是哈密顿图的新定理，至今还写在一些图论书中，在国际上非常有影响。

关键词：互素 公约数