初等数论(严蔚敏版)12 第五章二次同余式与平方剩余

《初等数论(严蔚敏版)12 第五章二次同余式与平方剩余》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《初等数论》习题解答（第三版）新乡学院第五章二次同余式与平方剩余1/38《初等数论》习题解答（第三版）新乡学院§5.1一般二次同余式21、在同余式yA0(modp)中，若p

2、A，试求出它的一切解来。解：若p

3、A，则A0(modp)，上同余式即为2y0(modp)22从而p

4、y，即有p

5、y。易见，当2为偶数时，2，则pp，上同余式有解：22/38《初等数论》习题解答（第三版）新乡学院x0,p,2p,,(p1)p(mo

6、dp)，共有n2m1p个解2当21为奇数时，pp，上同余式有解：111x0,p,2p,,(p1)p(modp)，共有n2m1p个解。3/38《初等数论》习题解答（第三版）新乡学院22、证明：同余式abaxbxc0(modm),(2a,m)122(1)有解的充分必要条件是xq(modm),qb4ac(2)有解，并且前一同余式的一切解可由后一同余式的解导出。证明：因(2a,m)1，故a用4a乘(1)后再配方，即得22(2axb)q

7、0(modm),qb4ac仍记2axb为x，即有2xq(modm)由以上讨论即知若xx(modm)为(1)的解，0则x2axb(modm)为(2)的解，必要性得证。04/38《初等数论》习题解答（第三版）新乡学院反之，若(2)有一解xx(mod)m，即有：022x80(mod),mqb4ac0由于(2a,m)1，故2axbx(modm)有解xx(modm)0122即有：(2axb)(b4ac)0(mod)m12即有：4(aaxbxc)0(mod)m112由a

8、，即有：axbxc0(mod)m11即xx(mod)m为(1)的解，充分性得证。1由充分性的讨论即知(1)的解可由(2)的解导出。5/38《初等数论》习题解答（第三版）新乡学院§5.2单质数的平方剩余与平方非剩余m1、求出模()的平方剩余与平方非剩余。dadp1解：p37,18，由书中定理2知，2模p37的简化剩余系中18个平方剩余分别与序列2221,2,,186/38《初等数论》习题解答（第三版）新乡学院例2．试判断下述同余方程是否是有解。2（1）27(mod37)2（2）

9、2(mod37)2（3）3(mod17)中之一数同余，而22222211,24,39,416,525,636,222712,827,97,222221026,1110,1233,1321,1411,222153,1634,1730,21828.7/38《初等数论》习题解答（第三版）新乡学院故模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，1

10、5，17，18，19，20，22，23，24，29，31，32，358/38《初等数论》习题解答（第三版）新乡学院2、()i应用前几章的结果证明:模p的简化剩余系中一定有平方剩余及平方非剩余存在，(ii)证明两个平方剩余的乘积是平方剩余;平方剩余与平方非剩余的乘积是平方非剩余。(iii)应用(i)、(ii)证明：模p的简化剩余系中平方剩余与平p1方非剩余的个数各为。22证明：(i)因为11(modp),1为模p的简化剩余系中的平方剩余。若模p的简化剩余系中均为平方剩余，考虑模p的绝对最小9/38《初等

11、数论》习题解答（第三版）新乡学院简化剩余系：p1p1,...,1,1,...,22p1它们的平方为模p下的个数：222p2(1),(2),...()2p1由假设模p的简化剩余系中任一个数与上个数同余，2而模p的简化剩余系中有p个数，故必有两个互相同余，矛盾。10/38《初等数论》习题解答（第三版）新乡学院从而必有平方非剩余存在。p1p1(ii)若a,b为平方剩余，则a21(modp),b21(modp)p1p1故(ab)21(modp),(p1)rr,2从而ab也

12、为平方剩余。若a为平方剩余，b为平方非剩余，则p1p1a21(modp),b21(modp)p1故(ab)21(mod),p从而ab为平方非剩余。(iii)设a,...,a为模p的简化剩余系中的平方剩余；1r11/38《初等数论》习题解答（第三版）新乡学院a,...,a为模p的简化剩余系中的平方非剩余。r1p1由(ii)知，aa,...,aa为平方非剩余，显然互不同余。r11r1r故r(p1)r,