Question

8．存在最小的合数n，使得2^n-1≡1（modn）成立，则n的值为（　　）

• A． 327
• B． 341
• C． 331
• D． 355

Answer 1

分析 若2^n-1 mod n=1，则2^n-1-1 mod n=0，进而可得${2}^{\frac{n-1}{2}}-1$必为质数，即$\frac{n-1}{2}$为质数，逐一分析四个答案，可得结论．

解答 解：1 mod n=1恒成立，
若2^n-1 mod n=1，则2^n-1-1 mod n=0，
则n必为奇数，
则n-1为偶数，
故2^n-1-1=（${2}^{\frac{n-1}{2}}+1$）（${2}^{\frac{n-1}{2}}-1$） mod n=0，
由n使满足2^n-1≡1（modn）成立的最小合数，
则${2}^{\frac{n-1}{2}}-1$必为质数，则$\frac{n-1}{2}$为质数，
当n=327时，$\frac{n-1}{2}$=163是质数，满足条件；
当n=341时，$\frac{n-1}{2}$=170不是质数，不满足条件；
当n=331时，$\frac{n-1}{2}$=165不是质数，不满足条件；
当n=355时，$\frac{n-1}{2}$=177不是质数，不满足条件；
故选：A

点评 本题考查的知识点是同余与整除，其中正确理解${2}^{\frac{n-1}{2}}-1$必为质数，即$\frac{n-1}{2}$为质数，是解答的关键．