- 运用CRT求解：
\(\begin{eqnarray*}
x &\equiv& 8 \pmod{11}\\
x &\equiv& 3 \pmod{19}
\end{eqnarray*}\)
- $x=8 \times 19 \times 7 + 3 \times 11 \times 7 = 1295\equiv 41$
- 运用CRT求解：
\(\begin{eqnarray*}
x & \equiv & 1\pmod{5}\\
x & \equiv & 2\pmod{7}\\
x & \equiv & 3\pmod{9}\\
x & \equiv & 4\pmod{11}
\end{eqnarray*}\)
- $x = 1 \times 693 \times 2 + 2 \times 495 \times 3 + 3 \times 385 \times 4 + 4 \times 315 \times 8 = 19056 \equiv 1731 \pmod {3465}$
- 手动计算$2000^{2019} \pmod{221}$，不允许使用电脑或者其他电子设备。[提示：这是一道看上去与中国剩余定理无关的计算题。]
- $13 \times 17 = 221$
- $2000\mapsto\langle 11,11 \rangle$
- $\langle 11^{2019}, 11^{2019}\rangle=\langle 11^3, 11^3\rangle=\langle 5,5\rangle$
- $x = 5 \times 17 \times -3 + 5 \times 13 \times 4= 5$
- 设$m$和$n$为互素的正整数，$a>0$为一个正整数，如果 \(\begin{eqnarray*}
x &\equiv& a \pmod{m}\\
x &\equiv& a \pmod{n}
\end{eqnarray*}\)$x$模$mn$等于什么？为什么？[提示：这是一道看上去与中国剩余定理相关的问题。]
- 为$a$，计算$x=a\times(n\times n^{-1}+m\times m^{-1})$，求$n,m$对应逆元时，由于$gcd(n,m)=1$，由贝祖定理知，$n\times n^{-1}+m\times m^{-1}=gcd(m,n)=1$，代入可得$x=a$
- 设$p$和$q$是不同的两个素数，请证明$p^{q-1} + q^{p-1} \equiv 1 \pmod{pq}$。
- 设$x = p^{q-1} + q^{p-1}\pmod{pq}$，由斌头剩余定理知，$x\equiv 1\pmod p, x\equiv 1 \pmod q$
- 这样的$x$必然为1
- 设$m$和$n$为互素的正整数，且$m, n > 2$。证明$mn$无原根（等价于，$\mathbb{Z}_{mn}^*$ 不是循环群）。 [提示：根据欧拉定理，对任意与$mn$互素的正整数$a$ ，$a^{\phi(mn) }\equiv 1 \pmod{mn}$，那么证明只需要说明必然存在比$\phi(mn)$小的值$s$使得$a^s \equiv 1 \pmod{mn}$。]
- $\mathbb{Z}_{mn}^* \mapsto\mathbb{Z}_m^*\times\mathbb{Z}_n^*，1\mapsto\langle 1,1 \rangle$
- 对于任意的$\langle a,b \rangle$，存在$a^{m-1}\equiv 1 \pmod m, b^{n-1}\equiv 1 \pmod n$，又$gcd(m-1,n-1)\geq 2$，故当$s=lcm(m-1,n-1)=\frac{(m-1)(n-1)}{gcd}$，我们会有$\langle a^s,b^s \rangle=\langle 1,1 \rangle$，$s<\phi(mn)$，则$\mathbb{Z}_{mn}^*$不存在阶为$\phi(mn)$的元素
- 实现一个利用CRT求解同余方程的程序（Python或者C语言都可以）。
# check prime # get inverse # mul and simplify - 使用CRT证明定理5.8。
- 由条件知，$\forall i,a^{n-1}\equiv a^{kp_i}\equiv 1\pmod p_i$
- 由CRT定理知，存在模$n=p_1…p_i$的唯一解$x$，故$a^{n-1}\pmod n$为满足这个性质的唯一解
- 请使用第一同构定理证明定理10.4中定义的映射$\phi$的单射性。
- 定义同态映射$\psi(x) = (x\pmod p, x \pmod q)$，易知$\psi$保持群操作，令$\mathbb{K}=Ker \psi=\lbrace 0 \rbrace$
- 则$\mathbb{Z}_{pq}/\mathbb{K}\mapsto\mathbb{Z}_{pq}$，即$\vert\mathbb{Z}_{pq}/\mathbb{K} \vert = \vert \mathbb{Z}_{pq} \vert$
- 由第一同构定理知，$\mathbb{Z}_{pq}/\mathbb{K} \cong \mathbb{Z}_p \times \mathbb{Z}_q$，则$\psi$为满射且单射
- 完成定理10.4的证明，即证明$\mathbb{Z}_n^*$与$\mathbb{Z}_p^* \times \mathbb{Z}_q^*$同构。
- 定义从$\mathbb{Z}_n$到$\mathbb{Z}_p\times\mathbb{Z}_q$的映射$\phi$为：\(\phi(x)=([x \mod p],[x \mod q])\)
- 证明$\phi$是一种双射，满射显然，由中国剩余定理，任意序对中的两个同余式在模$n$下有唯一解。对任意$a,b<n$，若有$([a \mod p],[a \mod q]) = ([b \mod p],[b \mod q])$，则$a=b$，单射性得证
- $\phi(a\times b ) = ([a \times b \mod p],[a \times b \mod q]) = ([a \mod p],[a \mod q])\times ([b \mod p],[b \mod q])=\phi(a)\times\phi(b)$
- 利用中国剩余定理证明欧拉Phi函数$\phi$是积性函数，即证明对任意互素的正整数$m,n > 1$，有$\phi(mn) = \phi(m) \phi(n)$。
- $x^{\phi(mn)}\equiv 1\mod mn,x^{\phi(m)\phi(n)}\equiv x^{\phi(m)}\equiv 1\mod m,x^{\phi(m)\phi(n)}\equiv x^{\phi(n)}\equiv 1\mod n$
- 则存在$x^{\phi(m)\phi(n)}=1\times n\times n^{-1} + 1 \times m \times m^{-1} = gcd(m,n)=1\mod mn$，故$x^{\phi(mn)}=x^{\phi(m)\phi(n)}\equiv 1\mod mn$
- 即$\phi(mn)=\phi(m)\phi(n)$
- PS:$nr + ms = 1,n^{-1}=r,m^{-1}=s$
- 请证明存在无穷多的正整数$n$使得$4n^2 + 1$可同时被$5$和$13$整除。[提示：分别考虑$n$满足何种条件可被$5$或$13$整除，于是得到了两条同余式，剩下的任务就是把$n$构造出来。]
- $4n^2+1\equiv 0 \pmod {13} \Leftrightarrow n^2 \equiv 3 \pmod {13}$，必然存在$n\equiv \pm 4\pmod {13}$
- $4n^2+1\equiv 0 \pmod {5} \Leftrightarrow n^2 \equiv 1 \pmod {5}$，必然存在$n\equiv \pm 1\pmod {5}$
- 由中国剩余定理知，存在上式存在模$n$下的解，则对于$\mathbb{N}$，存在无穷多的解
PREVIOUSCINTA-HW5/6
NEXTCINTA-HW8