习题七

作者: 洛玖言 | 来源:发表于2019-10-16 17:20 被阅读0次

【Python爬虫】-笨办法学 Python 习题01-10
整数与多项式-【目录】
习题七
11月7日-4期C语言学习总结
【Python爬虫】-笨办法学 Python 习题18-26
【Python爬虫】-笨办法学 Python 习题18-26
【Python爬虫】-笨办法学 Python 习题27-34
2019-05-19
【Python爬虫】-笨办法学 Python 习题27-34
【Python爬虫】-笨办法学 Python 习题13-17

习题七

1

解下列同余方程：
（i） $32x\equiv12\pmod{8}$
（ii） $28x\equiv 124\pmod{116}$
（iii） $5x\equiv44\pmod{81}$

Sol:
(i)
$(32,8)=8$ ，又 $8\not|\,12$
所以该同余方程无解

(ii)
$(28,116)=4$ ，又 $4|124$
所以该同余方程有 4 个解
$7x\equiv31\equiv2\pmod{29}$
$28x\equiv-x\equiv8\pmod{29}$
得到一解为 $x_0=-8$
所以该同余方程的解为：
$x\equiv -8+29t\pmod{116},\;\;t=0,1,2,3$

(iii)
$(5,81)=1$ ，又 $1|44$
$5x\equiv44\pmod{81}$
$10x\equiv88\equiv7\pmod{81}$
$80x\equiv-x\equiv56\pmod{81}$
$x\equiv-56\equiv25\pmod{81}$
所以改同余方程的解为：
$x\equiv 25\pmod{81}$

2

解下列一次同余方程组：
（i） $x\equiv1\pmod{3},\,x\equiv1\pmod{5},\,x\equiv2\pmod{7}$
（ii） $x\equiv1\pmod{4},\,x\equiv2\pmod{5},\,x\equiv3\pmod{9}$ .

Sol:
(i)
$M_1=m_2m_3=35,\;35M_1^{-1}\equiv2M_1^{-1}\equiv1\pmod{3}$
$4M_1^{-1}\equiv M_1^{-1}\equiv2\pmod{3}$
$M_2=m_1m_3=21,\;21M_2^{-1}\equiv M_2^{-1}\equiv1\pmod{5}$
$M_3=m_1m_2=15,\;15M_3^{-1}\equiv M_3^{-1}\equiv1\pmod{7}$
同余方程的解为：
$x\equiv 35\cdot2+21+15\cdot2\equiv16\pmod{105}$

(ii)
$M_1=m_2m_3=45,\;45M_1^{-1}\equiv M_1^{-1}\equiv1\pmod{4}$
$M_2=m_1m_3=36,\;36M_2^{-1}\equiv M_2^{-1}\equiv1\pmod{5}$
$M_3=m_1m_2=20,\;20M_3^{-1}\equiv2M_3^{-1}\equiv1\pmod{9}$
$10M_3^{-1}\equiv M_3^{-1}\equiv5\pmod{9}$
同余方程的解：
$x\equiv 45\cdot1\cdot1+36\cdot1\cdot2+20\cdot5\cdot3\equiv57\pmod{180}$

5

求 $2^{400}$ 被 319 除得的余数.

Sol:
$\varphi(319)=280$
所以有 $2^{280}\equiv1\pmod{319}$
$\begin{aligned} 2^{400}\equiv&2^{120}\equiv(2^{10})^{12}\equiv(67)^{12}\\ \equiv&(4489)^6\equiv(23)^6\equiv(529)^3\\ \equiv&210\cdot210\cdot210\equiv111\pmod{319} \end{aligned}$

8

设 $n$ 为正整数，证明必有 $n$ 个连续的整数，其中每一个数都具有平方因子 (即被某个大于 1 的完全平方数整除).

Sol:
我们要找连续的 $n$ 个整数： $x-(n-1),x-(n-2),\cdots,x-1,x$
每个数都有平方因子，即对任意的 $0\leqslant i \leqslant n-1$ 都存在素数 $p_i$
$p^2_i\;|\;x-i$
找 $n$ 个不同的素数 $p_i$ 有
$\begin{aligned} &x\equiv0\pmod{p_0^2}\\ &x\equiv1\pmod{p_1^2}\\ &\cdots\\ &x\equiv n-1\pmod{p_{n-1}^2} \end{aligned}$
又易知 $(p_0^2,p_1^2,\cdots,p_{n-1}^2)=1$
所以由中国剩余定理可知，该同余方程组必有解
所以存在这样的 $x$ 有对任意的 $0\leqslant i \leqslant n-1$ 都存在素数 $p_i$
$p^2_i\;|\;x-i$
得证.