41.
选5k+1型的数即用5除其余数为1的数20个,
1,6,11,.,96
再选5k+2型的数即用5除其余数为2的数20个,
2,7,12,.,97
再任选一个能被5整除的数(即5k型),比如选取5,
总共41个,即从1-99的所有自然数中最多能选出41个数,使其中任意两数之和都不能被5整除.
理由是:
选了全部的5k+1型的数,就不能再选5k+4型的数,因为5k+4型的数必与某个5k+1型的数之和能被5整除,同理选了全部的5k+2型的数,就不能再选5k+3型的数,另外能被5整除的数只能选1个,因为2个能被5整除的数之和也一定被5整除.(2楼的选19个本身是5的倍数的数是错的).