是否存在一个正整数n,满足n能被2000个不同质数整除,并且2^n+1能被n整除如题,一道美国数学竞赛题

Question

是否存在一个正整数n,满足n能被2000个不同质数整除,并且2^n+1能被n整除
如题,一道美国数学竞赛题

Answer 1

存在.我们用归纳法来证明一个更一般的
命题：对每一个自然数k都存在自然数n=n(k),满足n | 2n+1,3 | n 且 n 恰好能够被k个互不相同的质数整除.
当k=1时,n(1)=3即可使命题成立.
假设对於k≥1存在满足要求的n(k)=3r．t,其中r≥1且3不能整除t.於是n=n(k)必为奇数,可得3 | 22n-2n+1.利用恒等式 23n+1=(2n+1)(22n-2n+1)可知3n | 23n+1.跟据下面的引理,存在一个奇质数p满足p | 23n+1但是p不能整除2n+1.於是自然数n(k+1)= n(k)．3p满足命题对於k+1 的要求.归纳法完成.
引理：对於每一个整数a>2,存在一个质数p 满足p|a3+1 但是p不能整除a+1 .
证明：(反证法) 假设对某个a>2引理不成立：即任何能整除a3+1的素因子也能整除a+1.
由於a3+1=(a2-a+1)(a+1),所以有a2-a+1 的每一个质因子都要整除a+1.
而由恒等式a2-a+1=(a+1)(a-2)+3得知,如果素数p能整除a2-a+1,便能整除a+1,所以能整除3=(a2-a+1)-(a+1)(a-2),这说明能够整除a2-a+1 的唯一质数是3.换言之,a2-a+1是3的方幂.
因为a+1是3的倍数,所以a-2也是3的倍数.於是a2-a+1 能够被3整除,但不能被9整除.故得a2-a+1恰等於3.
另一方面,由a>2知a2-a+1>3 .这个矛盾完成了引理的证明.