(1982年 美 国 奥 赛 题 ) 证 明 存 在 一 个 正 整 数 k

野 菜 花

使 得 k*2^n+1 对 每 一 个 正 整 数 n， 均 为 合 数 。

www.ddhw.com

 

野 菜 花

Use the Chinese Remain Theorem. It IS very difficult, I doubt whether any people could solve it during the exam time. www.ddhw.com

野 菜 花

I agree with you that they must be crazy to give such difficult problem as a test question, and I am very sorry I did not read the solution carefully before I posted the problem. (So I am crazy too , although I am not on purpose.)  I thought a test problem would not be too difficult for people like you. You have done a great job. I don't understand how  people could give the solution without a computer.  I think through your hard and creative work, you could  master these skills in number theory better, hopefully you would not regret  having spent time on this problem.   Let me post their solution here, Claim1: For any n, at least one of the following is true: a)n=1(mod2) b)n=1(mod3) c)n=2(mod4) d)n=4(mod8) e)n=0(mod12) f)n=8(mod24)   Pf: If n is odd, a) is true; if 2 divides n but 4 not, then c) is true; if 4 divides n but 8 not, then d) is true;www.ddhw.com consider n=8m, if m=3k, then e) is true if m=3k+1,then f) is true if m=3k+2, then b) is true//   Notice: 2^2=1(mod3) 2^3=1(mod7) 2^4=1(mod5) 2^8=1(mod17) 2^12=1(mod13) 2^24=1(mod 241)   Therefore case a) n=1(mod2) or n=2m+1, then k*2^n+1=k*2^(2m+1)+1=2k*2^2m+1=2k+1(mod3) Similarly, we have case b) K*2^n+1=2k+1(mod7)www.ddhw.com case c) k*2^n+1=4k+1(mod5) case d) k*2^n+1=16k+1(mod17) case e) k*2^n+1=k+1(mod13) case f) k*2^n+1=256k+1(mod241)     Thus, if k satisfies all the followings, then k*2^n+1 is divisible by at least one of 3,7,5,17,13,241, therefore k*2^n+1 is not prime. 2k+1=0(mod3) 2k+1=0(mod7) 4k+1=0(mod5) 16k+1=0(mod17) k+1=0(mod13) 256k+1=0(mod241)  www.ddhw.com But those congruences are equivalent to the followings: k=1(mod3) k=3(mod7) k=1(mod5) k=1(mod17) k=-1(mod13) k=16(mod241)   Since all 3,7,5,17,13,241 are primes, according to the Chinese Remainder Theorem, there must be solutions. Actually, k=1207426+5592405m             www.ddhw.com

野 菜 花

Each USAMO has 5 question in various levels for 3.5 hours. I agree with both of you, I really doubt, any one could solve this problem during the exam time. www.ddhw.com