Question

8．存在最小的合數(shù)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，進(jìn)而可得${2}^{\frac{n-1}{2}}-1$必為質(zhì)數(shù)，即$\frac{n-1}{2}$為質(zhì)數(shù)，逐一分析四個答案，可得結(jié)論．

解答 解：1 mod n=1恒成立，
若2^n-1 mod n=1，則2^n-1-1 mod n=0，
則n必為奇數(shù)，
則n-1為偶數(shù)，
故2^n-1-1=（${2}^{\frac{n-1}{2}}+1$）（${2}^{\frac{n-1}{2}}-1$） mod n=0，
由n使?jié)M足2^n-1≡1（modn）成立的最小合數(shù)，
則${2}^{\frac{n-1}{2}}-1$必為質(zhì)數(shù)，則$\frac{n-1}{2}$為質(zhì)數(shù)，
當(dāng)n=327時，$\frac{n-1}{2}$=163是質(zhì)數(shù)，滿足條件；
當(dāng)n=341時，$\frac{n-1}{2}$=170不是質(zhì)數(shù)，不滿足條件；
當(dāng)n=331時，$\frac{n-1}{2}$=165不是質(zhì)數(shù)，不滿足條件；
當(dāng)n=355時，$\frac{n-1}{2}$=177不是質(zhì)數(shù)，不滿足條件；
故選：A

點(diǎn)評 本題考查的知識點(diǎn)是同余與整除，其中正確理解${2}^{\frac{n-1}{2}}-1$必為質(zhì)數(shù)，即$\frac{n-1}{2}$為質(zhì)數(shù)，是解答的關(guān)鍵．