四川省成都市第七中学高一年级竞赛数学数论专题讲义：11.模为素数的二次剩余

由天下分享时间：2024/12/16 16:32:57 加入收藏我要投稿点赞

高一竞赛数论专题 11.模为素数的二次剩余

设素数p?2,d是整数,pd.如果同余方程x?d(modp)有解,则称d是模p的二次剩余,若无解,则称d是模p的二次非剩余.

注意到p|d.则同余方程x?d?0(modp),则其有且只有一解x?0(modm).

若p?2,且pd.则同余方程x?d(mod2)为x?1(mod2)有且只有一解x?1(mod2).

2222p?1p?1个模p的二次剩余,个模p的二次非剩222余.此外,若d是模p的二次剩余,则同余方程x?d(modp)的解数为2.

1.设素数p?2,证明在模p的一个既约剩余系中,恰有

2.(Euler判别法)设素数p?2,pd,那么,d是模p的二次剩余的充要条件是d的二次非剩余的充要条件是dp?12p?12?1(modp);d是模p

??1(modp).

3. 若素数p?2,证明：?1是模p的二次剩余的充要条件是p?1(mod4).

??p?1??当p?1(mod4)时,????!???1(modp).

??2??

4.设p是奇素数,证明：1,2,?j2?p(p?1),p?1中全体模p的二次剩余之和S??p???.

24j?1?p?p?122p?12?j2?p(p2?1)p(p?1)由此可以证明当p?1(mod4)时,p?????.

p244j?1??

高一竞赛数论专题 11.模为素数的二次剩余解答

设素数p?2,d是整数,pd.如果同余方程x?d(modp)有解,则称d是模p的二次剩余,若无解,则称d是模p的二次非剩余.

注意到p|d.则同余方程x?d?0(modp),则其有且只有一解x?0(modm).

若p?2,且pd.则同余方程x?d(mod2)为x?1(mod2)有且只有一解x?1(mod2).

2222p?1p?1个模p的二次剩余,个模p的二次非剩222余.此外,若d是模p的二次剩余,则同余方程x?d(modp)的解数为2.

1.设素数p?2,证明在模p的一个既约剩余系中,恰有证明：取模p的绝对最小既约剩余系?p?1p?1,??1,22,?1,1,,p?1p?1?1,. 22,(p?1p?12?1)2,(). 22d是模p的二次剩余当且仅当d?(?22p?12p?1),(??1)2,22,(?1)2,12,,(2由于(?j)?j(modp),所以d是模p的二次剩余当且仅当d?1,p?1p?12?1)2,(). 22当1?i?j?p?1p?1时,2?i?j?p?1,1??i?j?0,i2?j2?(i?j)(i?j)??0(modp). 22,(p?1p?12p?1个. ?1)2,()给出了模p的全部二次剩余,共有

222p?1个必为模p的二次非剩余. 2所以d?1,2由于模p的既约剩余系(简系)有p?1个数,所以另外的

p?1,使得x?i(modp)是同余方程x2?d(modp)的2p?1p?1p?1p?1解,于是在模p的绝对最小既约剩余系?,??1,,?1,1,,?1,.中有且仅有

2222当d是模p的二次剩余时,必存在唯一的i,1?i?x??i(modp)是同余方程x2?d(modp)的解,所以解数为2.

2.(Euler判别法)设素数p?2,pd,那么,d是模p的二次剩余的充要条件是d的二次非剩余的充要条件是dp?12p?12?1(modp);d是模p

??1(modp).

p?12证明：首先来证明对任一d,pd,d由Euler定理知道dp?1?1(modp),dp?12p?12??1(modp)有且仅有一个成立.

?1(modp).因此(d?1)(dp?12?1)?0(modp).

由于素数p?2即(dp?12?1)?(dp?12?1)?2.

p?12所以对任一d,pd,dp?12?1(modp),d??1(modp)有且仅有一个成立.

p?12下面来证明d是模p的二次剩余的充要条件是d?1(modp).

2先证必要性(?)若d是模p的二次剩余,则必有x0使得x0?d(modp), 因此有xp?10?(x)20p?12?dp?12(modp).

p?10由于pd,所以p再证充分性,若dp?12x0.由Euler定理知道x?1(modp),所以dp?12?1(modp).