保证一定存在两个数是互质的

过路人 在推想与论证中出题，  部分网友讨论，不针对任何人。

12．从1到100这100个自然数中，至少要取出多少个数，才能保证一定存在两个数是互质的。

小豆120

1，2，4，6，8，。。。98，100共51个数，
至少要取出51=52个数，第52个数一定与2互质。

小豆老师，你上面列的这51个数中有个1比较特殊，1与任何自然数都互质。应该先取2，4，6，8，。。。98，100共50个数，
至少要再取一个，即取出51个数，第51个数一定与2互质。
公约数最有且只有1的两个数叫做互质数。

eagle119

如果取出的数是可以挑选的,最少2个就够了.
如果取出的数字是随意的,从最坏的角度出发,先拿到1和所有的非质数(假设是n个),然后拿到1个质数就行,则最多要取n+2个

注意其中的“保证”两个字，是不充许挑的，必须考虑最不利因素的。
你说先拿1和所有的非质数，这句话值得商榷。比如在1--10中，先取1，4，6，8，9，10，共6个，加2为8个，明显不行。何况1与所有非质数都互质，在非质数中也有互质的情况，例如4，9，49等等。

老杨

119，你可能把互质的意思理解错了。

存在50个数，两两不互质：2，4，6，...，100；
任意51个数，必定存在两数相邻，那么这两个数就互质。
因此问题的答案是51。

答案只能是51
本题应作一个反向的思考，在这100个自然数中，最多能取出几个数，并保证其中不会存在任何一对互质数。很显然，如果我们把所给数中的所有偶数取出来，其中就不会存在任何一对互质数。而在所给的100个自然数中，偶数共有50个。如果取出第51个，无论如何，这51个数中必然会有两个是相邻的自然数。而任意两个相邻的自然数必定是互质数。要保证其中不会存在任何一对互质数，最多能取出50个数。反之，要保证其中一定存在两个数是互质的，最少要取51个数。

这道题我们可以进行反向的思考。我们把其中的50个偶数取出，其中一定不会存在两个数是互质数。如果再取出第51个，则这51个数中必然会有两个是相邻的自然数，而相邻的任意两个自然数一定是互质数。所以本题的答案应为至少取出51个数。