内容发布更新时间 : 2024/11/8 12:16:54星期一 下面是文章的全部内容请认真阅读。
《初等数论》习题解答（第三版）广东石油化工学院
无多于(p?1?)n个解，而xp?1?1?0(mpo d恰)有p?1个解，
xp?1?a?0(mo必有pdn)个解。
2．设n是整数，（a，m）=1，且已知同余式xn?a(modm)
有一解x?x0(modm)，证明这个同余式的一切解可以 表成x?yx0(modm)
其中y是同余式yn?1(modm)的解。
证明：设x?x0,x?x1(modm)均是xn?a(modm)的解， 则x1n?x0n?a(modm)，
（a，m）=1 ， ? （x0，m）= (x1，m) = 1
则由第三章定理3．3知，必存在y，使 yx0?x1(modm)，
? ynx0n?x1n?x0n(modm) ．
故原同余式的任一解可表示为x?yx0(modm) 而y满足yn?1(modm)
3．设(a, m) = 1，k与m是正整数，又设x0k ? a (mod m)，证明同余方程
xk ? a(mod m)
的一切解x都可以表示成x ? yx0 (mod m)，其中y满足同余方程yk ? 1 (mod m)。 解：设x1是xk ? a(mod m)的任意一个解，则一次同余方程yx0 ? x1 (mod m)有解y，再由yka ? ykx0k ? (yx0)k ? x1k ? a (mod m)得yk ? 1 (mod m)，即x1可以表示成x ? yx0 (mod m)，其中y满足同余方程yk ? 1 (mod m)；反之，易知如此形式的x是xk ? a(mod m)的解。
41 / 77
《初等数论》习题解答（第三版）广东石油化工学院
第五章 二次同余式与平方剩余 §1 一般二次同余式
1、 在同余式y2?A?0(modp?)中，若p?|A，试求出它的一切解来。 解：若p?|A，则A?0(modp?)，上同余式即为
y2?0(modp?)
从而p?|y2，即有p????2???|y。
????????易见，当??2?为偶数时，????，则p?2??p?，上同余式有解：
?2?x?0,p?,2p?,,(p??1)p?(modp?)，共有n?2m?1?p个解
????2???当??2??1为奇数时，p?p?，上同余式有解：
x?0,p??1,2p??1,,(p??1)p??1(modp?)，共有n?2m?1?p个解。
2、证明：同余式abax2?bx?c?0(modm),(2a,m)?1 (1)有解的充分必要条件是
x2?q(modm),q?b2?4ac (2)有解，并且前一同余式的一切解可由后一同余式的解导出。
证明：因(2a,m)?1，故a 用4a乘(1)后再配方，即得
(2ax?b)2?q?0(modm),q?b2?4ac
仍记2ax?b为x，即有
x2?q(modm)
由以上讨论即知若x?x0(modm)为(1)的解， 则x?2ax0?b(modm)为(2)的解，必要性得证。 反之，若(2)有一解x?x0(modm)，即有：
2x0?8?0(modm),q?b2?4ac
42 / 77
《初等数论》习题解答（第三版）广东石油化工学院
由于(2a,m)?1，故2ax?b?x0(modm)有解x?x1(modm) 即有：(2ax1?b)2?(b2?4ac)?0(modm) 即有：4a(ax12?bx1?c)?0(modm) 由a，即有：ax12?bx1?c?0(modm) 即x?x1(modm)为(1)的解，充分性得证。 由充分性的讨论即知(1)的解可由(2)的解导出。 §2 单质数的平方剩余与平方非剩余
1、 求出模
??()的平方剩余与平方非剩余。
damd解：p?37,序列12,22,p?1?18，由书中定理2知，模p?37的简化剩余系中18个平方剩余分别与2,182
例2．试判断下述同余方程是否是有解。 （1）?2?27(mod37) （2）?2?2(mod37) （3）?2?3(mod17) 中之一数同余，而
12?1 ,22?4, 32?9, 42?16, 52?25, 62?36, 72?12, 82?27, 92?7,
2?26,2?10, 122?33, 132?21, 142?11, 152?3, 162?34, 172?30, 10 112?28. 18
故模37的平方剩余为：
1，3，4，7，9，10，11，12，16，21，25，26，27，30，33，34，36 而其它的18个数为模37的平方非剩余：
2，5，6，8，13，14，15，17，18，19，20，22，23，24，29，31，32，35
2． (i)应用前几章的结果证明:模p的简化剩余系中一定有平方剩余及平方非剩余存在，
43 / 77
《初等数论》习题解答（第三版）广东石油化工学院
(ii)证明两个平方剩余的乘积是平方剩余;平方剩余与平方非剩余的乘积是平方非剩余。 (iii)应用(i)、(ii)证明：模p的简化剩余系中平方剩余与平方非剩余的个数各为
p?1。 2证明：(i)因为12?1(modp),1为模p的简化剩余系中的平方剩余。若模p的简化剩余系中均为平方剩余，考虑模p的绝对最小简化剩余系：?p?1p?1 ,...,?1,1,...,22p?1个数： 2p (?12 ),?(22),?...(2)2它们的平方为模p下的
由假设模p的简化剩余系中任一个数与上
p?1个数同余，而模p的简化剩余系中有p个数，2故必有两个互相同余，矛盾。从而必有平方非剩余存在。
(ii)若
p?12a,b为平方剩余，则
ap?12?1(modp),bp?12?1(modp)故
(ab)??1(modp),(p?1)?r?r?p?12p?1,从而ab也为平方剩余。若a为平方剩余，b为平方2非剩余，则a故(ab)p?12?1(modp),bp?12??1(modp)
??1(modp),从而ab为平方非剩余。
(iii)设a1,...,ar为模p的简化剩余系中的平方剩余；ar?1,...,ap?1为模p的简化剩余系中的平方
非剩余。由(ii)知，ar?1a1,...,ar?1ar为平方非剩余，显然互不同余。故r?(p?1)?r,反之，由
ar?12,ar?1ar?2,...,ar?1ap?1为平方剩余知(p?1)?r?r,故r?3．证明：同余式x2?amodp?，?a,p??1的解是
p?1，得证。 2???mod? x??pQp，其中
??? p?2?a????2?2a???,Q??12?a?????2?a?2a?mopd?
?? 22?a?modp?Q,Q证明：若x2?amodp?有解，则x2?a?modp?有解，
44 / 77
?? 《初等数论》习题解答（第三版）广东石油化工学院
设其解是：x?2?modp?，即有： 22?a?modp?， 令22?a?kp?22?a而2?a????k?p??0?modp?? a?C?22????2?C?2?1??1??2?a?2???a??
?p?Qa ，p,Q 为整数
?2?a???p?Qa 由此两式即得：
?p?
2?a????2?a2??2?a???2?a??Q???
2a两式相乘得： 2?a?2???p2?aQ2?p2?aQ2?0?modp??
?p2?aQ2modp? 取Q?使得： QQ??1modp?
则 p2?Q???amodp? 故其解为 x??pQ?modp? 4．证明同余式x2?1?0?modp?,p?4m?1 的解是 x??1?22?????????2mp??mod?
证明：首先我们证明对任意n：p?n 有下式： ?n?1?!?p?n?!????1?因为??1?k?p?k?modp? ，于是 ?n?1?!???1?因此由威尔生定理得：
45 / 77
n?1nmo?dp
?p??1?p?n???1 mo?dp