高一竞赛数论专题 14.指数与原根(二)
1.设a为大于1的正整数,n?N.证明：n|?(a?1).
用指数解题的套路：先求出指数,再利用Fermat-Euler定理,最后利用指数的性质,得到整除关系式.
2.设n?1,n|(2?1),证明：3|n.
n*n
3.设第n(n?0)个Fermat数Fn?2?1.证明
n?1n?1n?1(1)?Fn(2)?2. (2)若素数p|Fn,则?p(2)?2. (3)Fn的素因子p?1(mod2).
2n(4)若Fn是素数,n?1,则2一定不是Fn的原根.
(5)若Fn是素数,则模Fn的任意一个二次非剩余必为Fn的原根. (6)若Fn是素数,则?3,?7都是原根. (7)n?1,Fn的素因子p?1(mod2
n?2).
4.设m?2?1(n?1),证明m是素数的充要条件是3
nm?12??1(modm).
高一竞赛数论专题 14.指数与原根(二)解答
1.设a为大于1的正整数,n?N.证明：n|?(a?1).
证明：因为a?1,所以n是满足a?1(moda?1)的最小正整数,即?an?1(a)?n. 由Euler定理知道a?(an*nnn?1)?1(modan?1).所以?an?1(a)|?(an?1)即n|?(an?1).
用指数解题的套路：先求出指数,再利用Fermat-Euler定理,最后利用指数的性质,得到整除关系式.
2.设n?1,n|(2?1),证明：3|n.
证明：显然n是奇数,设p是n的最小素因子,则p?3.我们证明p?3.从而3|n. 因为n|(2?1),所以p|(2?1).即2??1(modp),于是2由p是大于2的素数,所以由Euler定理知道2p?1nnn2nn?1(modp).
?1(modp).
设2对模p的指数为?p(2).则?p(2)|p?1,?p(2)|2n.于是?p(2)|(p?1,2n). 因为n是奇数,p?1是偶数,所以2|(p?1,2n),22(p?1,2n).
若奇素数q|(p?1,2n),则q|(p?1),q|n.从q|(p?1)知道q?p,又q|n,这与p是n的最小素因子矛盾. 所以(p?1,2n)?2.因为?p(2)|(p?1,2n),所以?p(2)|2.因为p?3,所以?p(2)?2. 即2?1(modp).于是p?3.
3.设第n(n?0)个Fermat数Fn?2?1.证明
n?1n?1n?1(1)?Fn(2)?2. (2)若素数p|Fn,则?p(2)?2. (3)Fn的素因子p?1(mod2).
22n(4)若Fn是素数,n?1,则2一定不是Fn的原根.
(5)若Fn是素数,则模Fn的任意一个二次非剩余必为Fn的原根. (6)若Fn是素数,则?3,?7都是原根. (7)n?1,Fn的素因子p?1(mod2证明：(1)22n?1nnn?2).
nn?1n?1?1?(22?1)(22?1)?Fn(22?1)所以Fn|(22?1).即22?1(modFn).
n?1注意到(2,Fn)?1,所以?Fn(2)|2.因为Fn?2?1?1(l?n),所以Fn所以?Fn(2)?2.
n?12l(2?1),(l?n).
2ln?1d(2)p|Fn,所以?p(2)|?Fn(2)?2.设?p(2)?2,d?n?1.即p|22?1,p22dd?1?1.
若d?n,则p|22?1?(22dd?1?1)(22?1),因此p|(22?1),即p|Fd?1,(d?n),这与Fermat数两两互素
n?1d?1d?1矛盾.所以d?n?1.即?p(2)?2.
(3)Fn的素因子p满足?p(2)?2.又?p(2)|?(p).即2nn?1n?1|p?1.于是p?1(mod2n?1).
12n?1(4)因为?Fn(2)?2.?(Fn)?2.但2?(1?1)?Cn?Cn?n?1(n?1),所以?Fn(2)??(Fn).
nn0所以2一定不是素数Fn的原根.
(5)若a是模Fn的二次非剩余,则由欧拉判别法知道aFn?12?a22n?1??1(modFn).
假设a不是Fn的原根,则?Fn(a)|?(Fn),?Fn(a)??(Fn). 又?(Fn)?2.于是?Fn(a)?2,k?2.即a设2?1?k?t,则t?0.
n2nkn2k?1(modFn),(k?2n?1).
aFn?12?a22n?1?a2k?t?(a2)2?1(modFn)(矛盾).
kt
四川省成都市第七中学高一年级竞赛数学数论专题讲义：14.指数与原根(二)
