NJUPT《信安數基》復習題

第 1 章

1. 設 a = 1859 , b = 1573 , a=1859, \quad b=1573, a=1859,b=1573, 計算 s , t , s, t, s,t, 使得 a s + b t = ( a , b ) a s+b t=(a, b) as+bt=(a,b) ，

運用廣義歐幾里得除法：
1859 = 1 ? 1573 + 286 1573 = 5 ? 286 + 143 286 = 2 ? 143 + 0 \begin{array}{rr} 1859&=&1 \cdot 1573&+&286 \\ 1573&=&5 \cdot 286&+&143 \\ 286&=&2 \cdot 143&+&0 \end{array} 18591573286?===?1?15735?2862?143?+++?2861430?
然后：
143 = ( ? 5 ) ? 286 + 1573 = ( ? 5 ) ? ( ( ? 1 ) ? 1573 + 1859 ) + 1573 = 6 ? 1573 + ( ? 5 ) ? 1573 = ( ? 5 ) ? 1859 + 6 ? 1573 \begin{array}{rr} 143&=&(-5) \cdot 286&+&1573 \\ &=&(-5) \cdot ((-1)\cdot 1573+1859)&+&1573 \\ &=&6\cdot 1573&+&(-5)\cdot 1573 \\ &=&(-5)\cdot 1859&+&6\cdot 1573 \end{array} 143?====?(?5)?286(?5)?((?1)?1573+1859)6?1573(?5)?1859?++++?15731573(?5)?15736?1573?
因此，整數 s = ? 5 , t = 6 s=-5,t=6 s=?5,t=6 使得 a s + b t = ( a , b ) . as+bt=(a,b). as+bt=(a,b).

2. 最大公約數 (4655, 12075)=

運用廣義歐幾里得除法：
12075 = 2 ? 4655 + 2765 4655 = 1 ? 2765 + 1890 2765 = 1 ? 1890 + 875 1890 = 2 ? 875 + 140 875 = 6 ? 140 + 35 140 = 4 ? 35 + 0 \begin{array}{rr} 12075&=&2 \cdot 4655&+&2765 \\ 4655&=&1 \cdot 2765&+&1890 \\ 2765&=&1 \cdot 1890&+&875 \\ 1890&=&2 \cdot 875&+&140 \\ 875&=&6 \cdot 140&+&35 \\ 140&=&4 \cdot 35&+&0 \end{array} 12075465527651890875140?======?2?46551?27651?18902?8756?1404?35?++++++?27651890875140350?
所以 ( 4655 , 12075 ) = 35 (4655, 12075) = 35 (4655,12075)=35.

3. 滿足 125 x + 17 y = ( 125 , 17 ) 125 x+17 y=(125,17) 125x+17y=(125,17) 的 x x x 和 y y y 分別為

運用廣義歐幾里得除法：
125 = 7 ? 17 + 6 17 = 2 ? 6 + 5 6 = 1 ? 5 + 1 5 = 5 ? 1 + 0 \begin{array}{rr} 125&=&7 \cdot 17&+&6 \\ 17&=&2 \cdot 6&+&5 \\ 6&=&1 \cdot 5&+&1 \\ 5&=&5 \cdot 1&+&0 \end{array} 1251765?====?7?172?61?55?1?++++?6510?
所以 ( 125 , 17 ) = 1. (125, 17) = 1. (125,17)=1.
1 = ( ? 1 ) ? 5 + 6 = ( ? 1 ) ? ( ( ? 2 ) ? 6 + 17 ) + 6 = 3 ? 6 + ( ? 1 ) ? 17 = 3 ? ( ( ? 7 ) ? 17 + 125 ) + ( ? 1 ) ? 17 = 3 ? 125 + ( ? 22 ) ? 17 \begin{array}{rr} 1&=&(-1) \cdot 5&+&6 \\ &=&(-1) \cdot ((-2)\cdot 6+17)&+&6 \\ &=&3\cdot 6&+&(-1)\cdot 17 \\ &=&3\cdot ((-7)\cdot 17+125)&+&(-1)\cdot 17\\ &=&3\cdot 125&+&(-22)\cdot 17 \end{array} 1?=====?(?1)?5(?1)?((?2)?6+17)3?63?((?7)?17+125)3?125?+++++?66(?1)?17(?1)?17(?22)?17?
因此，整數 x = 3 , y = ? 22 x=3,y=-22 x=3,y=?22 使得 125 x + 17 y = ( 125 , 17 ) . 125x+17y=(125,17). 125x+17y=(125,17).

4. a , b a, b a,b 是兩個正整數，則其最小公倍數 [ a , b ] = a ? b ( a , b ) [a, b]=\frac{a\cdot b}{(a,b)} [a,b]=(a,b)a?b?

5. 設 a , b a, b a,b 是兩個正整數，且有素因數分解:

a = p 1 α 1 ? p s α s , α i ≥ 0 ; b = p 1 β 1 ? p s β s , β i ≥ 0 ; i = 1 , … , s \large a=p_{1}^{\alpha_{1}} \cdots p_{s}^{\alpha_{s}}, \alpha_{i} \geq 0 ; \quad b=p_{1}^{\beta_{1}} \cdots p_{s}^{\beta_{s}}, \beta_{i} \geq 0 ; \quad i=1, \ldots, s a=p1α1???psαs??,αi?≥0;b=p1β1???psβs??,βi?≥0;i=1,…,s

則其最小公倍數 [ a , b ] = [a, b]= [a,b]= 最大公約數 ( a , b ) = (a, b)= (a,b)=

[ a , b ] = p 1 max ? ( α 1 , β 1 ) ? p s max ? ( α s , β s ) \large [a, b]=p_{1}^{\max(\alpha_{1},\beta_{1})} \cdots p_{s}^{\max(\alpha_{s},\beta_{s})} [a,b]=p1max(α1?,β1?)??psmax(αs?,βs?)?

( a , b ) = p 1 min ? ( α 1 , β 1 ) ? p s min ? ( α s , β s ) \large (a, b)=p_{1}^{\min(\alpha_{1},\beta_{1})} \cdots p_{s}^{\min(\alpha_{s},\beta_{s})} (a,b)=p1min(α1?,β1?)??psmin(αs?,βs?)?

6. 證明: 任意三個連續整數的乘積都被 6 整除，

對于任意的 n ∈ Z n\in Z n∈Z，三個連續整數乘積為 ( n ? 1 ) ? n ? ( n + 1 ) (n-1)\cdot n\cdot (n+1) (n?1)?n?(n+1)，

1. n = 2 k , k ∈ Z n=2k,k\in Z n=2k,k∈Z 時， 2 k 2k 2k 是 2 2 2 的倍數，所以 2 ｜ ( n ? 1 ) ? n ? ( n + 1 ) . 2｜(n-1)\cdot n\cdot (n+1). 2｜(n?1)?n?(n+1).
2. n = 2 k + 1 , k ∈ Z n=2k+1,k\in Z n=2k+1,k∈Z 時， n ? 1 = 2 k n-1=2k n?1=2k 是 2 2 2 的倍數，所以 2 ｜ ( n ? 1 ) ? n ? ( n + 1 ) . 2｜(n-1)\cdot n\cdot (n+1). 2｜(n?1)?n?(n+1).

所以對于任意的 n ∈ Z n\in Z n∈Z，有 2 ｜ ( n ? 1 ) ? n ? ( n + 1 ) . 2｜(n-1)\cdot n\cdot (n+1). 2｜(n?1)?n?(n+1). ①

1. n = 3 k , k ∈ Z n=3k,k\in Z n=3k,k∈Z 時， 3 k 3k 3k 是 3 3 3 的倍數，所以 3 ｜ ( n ? 1 ) ? n ? ( n + 1 ) . 3｜(n-1)\cdot n\cdot (n+1). 3｜(n?1)?n?(n+1).
2. n = 3 k + 1 , k ∈ Z n=3k+1,k\in Z n=3k+1,k∈Z 時， n ? 1 = 3 k n-1=3k n?1=3k 是 3 3 3 的倍數，所以 3 ｜ ( n ? 1 ) ? n ? ( n + 1 ) . 3｜(n-1)\cdot n\cdot (n+1). 3｜(n?1)?n?(n+1).
3. n = 3 k + 2 , k ∈ Z n=3k+2,k\in Z n=3k+2,k∈Z 時， n + 1 = 3 k + 3 n+1=3k+3 n+1=3k+3 是 3 3 3 的倍數，所以 3 ｜ ( n ? 1 ) ? n ? ( n + 1 ) . 3｜(n-1)\cdot n\cdot (n+1). 3｜(n?1)?n?(n+1).

所以對于任意的 n ∈ Z n\in Z n∈Z，有 3 ∣ ( n ? 1 ) ? n ? ( n + 1 ) . 3|(n-1)\cdot n\cdot (n+1). 3∣(n?1)?n?(n+1). ②

由①②且 ( 2 , 3 ) = 1 (2,3)=1 (2,3)=1，所以 6 ∣ ( n ? 1 ) ? n ? ( n + 1 ) . 6|(n-1)\cdot n\cdot (n+1). 6∣(n?1)?n?(n+1). 所以任意三個連續整數的乘積都被 6 整除，

7. 設 m > n m>n m>n 是正整數，證明 2 n ? 1 ∣ 2 m ? 1 2^{n}-1 \mid 2^{m}-1 2n?1∣2m?1 的充要條件是 n ∣ m n \mid m n∣m ，

充分性：

已知 n ∣ m n|m n∣m 成立，即有 m = q n m=q n m=qn，則
2 m ? 1 = 2 q n ? 1 = ( 2 n ? 1 ) [ 2 n ( q ? 1 ) + 2 n ( q ? 2 ) + ? + 2 n + 1 ] = ( 2 n ? 1 ) k \begin{aligned} 2^{m}-1 &=2^{q n}-1 \\ &=\left(2^{n}-1\right)\left[2^{n(q-1)}+2^{n(q-2)}+\cdots+2^n+1]\right.\\ &=\left(2^{n}-1\right) k \end{aligned} 2m?1?=2qn?1=(2n?1)[2n(q?1)+2n(q?2)+?+2n+1]=(2n?1)k?
因此 2 m ? 1 2^{m}-1 2m?1 可以整除 2 n ? 1 2^{n}-1 2n?1

必要性：
已知 2 m ? 1 2^{m}-1 2m?1 可以整除 2 n ? 1 2^{n}-1 2n?1，則
2 m ? 1 = ( 2 n ? 1 ) k = ( 2 n ? 1 ) [ 2 n ( q ? 1 ) + 2 n ( q ? 2 ) + ? + 2 n + 1 ] = 2 q n ? 1 \begin{aligned} 2^{m}-1 &=\left(2^{n}-1\right) k \\ &=\left(2^{n}-1\right)\left[2^{n(q-1)}+2^{n(q-2)}+\cdots+2^{n}+1]\right.\\ &=2^{q n}-1 \\ \end{aligned} 2m?1?=(2n?1)k=(2n?1)[2n(q?1)+2n(q?2)+?+2n+1]=2qn?1?
所以 x m = x q n x^{m}= x^{q n} xm=xqn， m = q n m=q n m=qn

因此 m m m 能夠整除 n n n 成立

8. 設 a = 666 , b = 1414 , a=666, \quad b=1414, a=666,b=1414, 計算 s , t , s, t, s,t, 使得 a s + b t = ( a , b ) a s+b t=(a, b) as+bt=(a,b) ，

運用廣義歐幾里得除法：
1414 = 2 ? 666 + 82 666 = 8 ? 82 + 10 82 = 8 ? 10 + 2 10 = 5 ? 2 + 0 \begin{array}{rr} 1414&=&2 \cdot 666&+&82 \\ 666&=&8 \cdot 82&+&10 \\ 82&=&8 \cdot 10&+&2 \\ 10&=&5 \cdot 2&+&0 \end{array} 14146668210?====?2?6668?828?105?2?++++?821020?
所以 ( a , b ) = 2 (a, b)=2 (a,b)=2
2 = ( ? 8 ) ? 10 + 82 = ( ? 8 ) ? ( ( ? 8 ) ? 82 + 666 ) + 82 = ( ? 8 ) ? 666 + 65 ? 82 = ( ? 8 ) ? 666 + 65 ? ( ( ? 2 ) ? 666 + 1414 ) = ( ? 138 ) ? 666 + 65 ? 1414 \begin{array}{rr} 2&=&(-8) \cdot 10&+&82 \\ &=&(-8) \cdot ((-8) \cdot 82+666)&+&82 \\ &=&(-8) \cdot 666&+&65\cdot 82 \\ &=&(-8) \cdot 666&+&65\cdot ((-2)\cdot 666 + 1414) \\ &=&(-138) \cdot 666&+&65\cdot 1414 \\ \end{array} 2?=====?(?8)?10(?8)?((?8)?82+666)(?8)?666(?8)?666(?138)?666?+++++?828265?8265?((?2)?666+1414)65?1414?
因此，整數 s = ? 138 , t = 65 s=-138,t=65 s=?138,t=65 使得 a s + b t = ( a , b ) . as+bt=(a,b). as+bt=(a,b).

9. 證明: 17 \sqrt{17} 17 ? 是無理數，

假設 17 \sqrt{17} 17 ? 是有理數, 則 ? p , q , \exists\ p, q, ? p,q, 使 17 = p q \sqrt{17}=\frac{p}{q} 17 ?=qp?，

所以存在互質的 p , q , p 2 = 17 q 2 p, q, p^{2}=17 q^{2} p,q,p2=17q2 ，素數 17 17 17 能夠整除 p 2 p^2 p2，所以 17 17 17 也能整除 p p p，

由于 q 2 = p 2 17 q^{2}=\frac{p^{2}}{17} q2=17p2? ，所以素數 17 17 17 能夠整除 q 2 q^2 q2，那么 17 17 17 也能整除 q q q，

所以 p p p 和 q q q 存在最大公因數 17. 17. 17. 與 p , q p, q p,q 互質矛盾，假設不成立， 17 \sqrt{17} 17 ? 是無理數得證，

第 2 章

1. 設 m = 13 m=13 m=13 ，則其絕對值最小完全剩余系（簡化剩余系等）為 { ? 6 , ? 5 , ? 4 , ? 3 , ? 2 , ? 1 , 0 , 1 , 2 , 3 , 4 , 5 , 6 } \{-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6\} {?6,?5,?4,?3,?2,?1,0,1,2,3,4,5,6}

2. 寫出模 21 的簡化剩余系 { 1 , 2 , 4 , 5 , 8 , 10 , 11 , 13 , 16 , 17 , 19 , 20 } \{1,2,4,5,8,10,11,13,16,17,19,20\} {1,2,4,5,8,10,11,13,16,17,19,20}

3. 寫出模 9 的完全剩余系（每個數為偶數） { 0 , 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 } \{0,2,4,6,8,10,12,14,16\} {0,2,4,6,8,10,12,14,16}

4. 證明: 設 m 1 , m 2 m_{1}, m_{2} m1?,m2? 是兩個互素的正整數，若 k 1 , k 2 k_{1}, k_{2} k1?,k2? 分別遍歷 m 1 , m 2 m_{1}, m_{2} m1?,m2? 的完全剩余系，則

m 1 ? k 2 + m 2 ? k 1 m_{1} \cdot k_{2}+m_{2} \cdot k_{1} m1??k2?+m2??k1? 遍歷模 m 1 m 2 m_{1} m_{2} m1?m2? 的完全剩余系，

5. φ ( 450 ) = 120 \varphi(450)=120 φ(450)=120

先分解 450 = 2 ? 3 2 ? 5 2 450=2 \cdot 3^2 \cdot 5^2 450=2?32?52，所以 φ ( 450 ) = ( 2 ? 1 ) ( 3 ? 1 ) ( 5 ? 1 ) ? 3 ? 5 = 120 \varphi(450)=(2-1)(3-1)(5-1)\cdot 3\cdot 5=120 φ(450)=(2?1)(3?1)(5?1)?3?5=120.

6. 利用模平方演算法計算 50 1 13 ? m o d ? 667 501^{13} \bmod 667 50113mod667; 31 2 13 ? m o d ? 667 312^{13} \bmod 667 31213mod667

50 1 13 ? m o d ? 667 = 163 501^{13} \bmod 667=163 50113mod667=163

31 2 13 ? m o d ? 667 = 468 312^{13} \bmod 667=468 31213mod667=468

7. 證明: 如果 p , q p, q p,q 是不同的素數，則 p q ? 1 + q p ? 1 ≡ 1 ( ? m o d ? p q ) p^{q-1}+q^{p-1} \equiv 1(\bmod p q) pq?1+qp?1≡1(modpq) ，

因為p,q是不同的素數，由費馬小定理，有 q p ? 1 ≡ 1 ? m o d ? p , p q ? 1 ≡ 1 ? m o d ? q q^{p-1}\equiv 1\bmod p,\ p^{q-1}\equiv 1\bmod q qp?1≡1modp, pq?1≡1modq，

所以存在 k 1 , k 2 ∈ Z k_1,k_2 \in Z k1?,k2?∈Z，使 q p ? 1 ? 1 = k 1 p , p q ? 1 ? 1 = k 2 q . q^{p-1}-1=k_1p,\ p^{q-1}-1=k_2q. qp?1?1=k1?p, pq?1?1=k2?q.

所以 ( q p ? 1 ? 1 ) ? ( p q ? 1 ? 1 ) = k 1 k 2 p q (q^{p-1}-1)\cdot (p^{q-1}-1)=k_1k_2pq (qp?1?1)?(pq?1?1)=k1?k2?pq，等式兩邊對 p q pq pq 取模得 p q ? 1 + q p ? 1 ≡ 1 ( ? m o d ? p q ) p^{q-1}+q^{p-1} \equiv 1(\bmod p q) pq?1+qp?1≡1(modpq)

8. 2003 年 5 月 9 日是星期五，則第 2 20080509 2^{20080509} 220080509 天是星期____

由費馬小定理， 2 6 ? m o d ? 7 2^6\bmod 7 26mod7， 20080509 ? m o d ? 6 = 3 , 2 3 ? m o d ? 7 = 1 20080509\bmod 6=3,\ 2^3\bmod 7=1 20080509mod6=3, 23mod7=1，星期六

9. 求 8 ? 9 ? 10 ? 11 ? 12 ? 13 ? m o d ? 7 = 6 8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 \cdot 13 \bmod 7=6 8?9?10?11?12?13mod7=6

威爾遜（Wilson）定理： ( p ? 1 ) ! ≡ ? 1 ? m o d ? p . (p-1)!\equiv -1\bmod p. (p?1)!≡?1modp.

8 ? 9 ? 10 ? 11 ? 12 ? 13 ≡ 6 ! ≡ ? 1 ≡ 6 ? m o d ? 7 8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 \cdot 13\equiv 6!\equiv-1\equiv 6\bmod 7 8?9?10?11?12?13≡6!≡?1≡6mod7

10. 證明: 如果 c 1 , c 2 , … , c φ ( m ) c_{1}, c_{2}, \ldots, c_{\varphi(m)} c1?,c2?,…,cφ(m)? 是模 m m m 的簡化剩余系，則 c 1 + c 2 + … + c φ ( m ) ≡ 0 ( ? m o d ? m ) c_{1}+c_{2}+\ldots+c_{\varphi(m)} \equiv 0(\bmod m) c1?+c2?+…+cφ(m)?≡0(modm) ，

11. 證明對任意的整數 a , ( a , 561 ) = 1 , a, \quad(a, 561)=1, a,(a,561)=1, 都有 a 560 ≡ 1 ? m o d ? 561 , a^{560} \equiv 1\bmod 561, a560≡1mod561, 但 561 561 561 是合數，

12. 設 a , b , c , m a,b,c,m a,b,c,m 是正整數, m > 1 , ( b , m ) = 1 \mathrm{m}>1, \quad(b, m)=1 m>1,(b,m)=1 并且 b a ≡ 1 ? m o d ? m , b c ≡ 1 ? m o d ? m , b^{a} \equiv 1 \bmod m, \quad b^{c} \equiv 1 \bmod m, ba≡1modm,bc≡1modm, 記 d = ( a , c ) , d=(a, c), d=(a,c), 證明 b d ≡ 1 ? m o d ? m ° b^{d} \equiv 1 \bmod m_{\circ} bd≡1modm°?

第 3 章

1. 求解一次同余式 33 x ≡ 44 ( ? m o d ? 121 ) ; 127 x ≡ 833 ( ? m o d ? 1012 ) ， 33 x \equiv 44(\bmod 121) ; 127 x \equiv 833(\bmod 1012) ， 33x≡44(mod121);127x≡833(mod1012)，

33 x ≡ 44 ( ? m o d ? 121 ) 33 x \equiv 44(\bmod 121) 33x≡44(mod121)：解 33 x ? 121 y = 44 33x-121y=44 33x?121y=44，
121 = 3 ? 33 + 22 33 = 1 ? 22 + 11 22 = 2 ? 11 + 0 \begin{array}{rr} 121&=&3 \cdot 33&+&22 \\ 33&=&1 \cdot 22&+&11 \\ 22&=&2 \cdot 11&+&0 \end{array} 1213322?===?3?331?222?11?+++?22110?
所以 ( 33 , 121 ) = 11. (33,121)=11. (33,121)=11.
11 = ( ? 1 ) ? 22 + 33 = ( ? 1 ) ? ( ( ? 3 ) ? 33 + 121 ) + 33 = ( ? 1 ) ? 121 + 4 ? 33 \begin{array}{rr} 11&=&(-1) \cdot 22&+&33 \\ &=&(-1) \cdot ((-3)\cdot 33+121)&+&33 \\ &=&(-1)\cdot 121 &+& 4\cdot 33 \end{array} 11?===?(?1)?22(?1)?((?3)?33+121)(?1)?121?+++?33334?33?
33 ? 4 ? 121 ? 1 = 11 33\cdot 4-121\cdot 1=11 33?4?121?1=11， 4 ( 33 ? 4 ? 121 ? 1 ) = 44 4(33\cdot 4-121\cdot 1)=44 4(33?4?121?1)=44， x = 5 + 11 k , k = 1 , 2 , ? ? , 10 x=5+11k,k=1,2,\cdots,10 x=5+11k,k=1,2,?,10

127 x ≡ 833 ( ? m o d ? 1012 ) 127 x \equiv 833(\bmod 1012) 127x≡833(mod1012)： 127 x ? 1012 y = 833 127x-1012y=833 127x?1012y=833
1012 = 7 ? 127 + 123 127 = 1 ? 123 + 4 123 = 30 ? 4 + 3 4 = 1 ? 3 + 1 3 = 3 ? 1 + 0 \begin{array}{rr} 1012&=&7 \cdot 127&+&123 \\ 127&=&1 \cdot 123&+&4 \\ 123&=&30 \cdot 4&+&3 \\ 4&=&1 \cdot 3&+&1 \\ 3&=&3 \cdot 1&+&0 \end{array} 101212712343?=====?7?1271?12330?41?33?1?+++++?1234310?
所以 ( 127 , 1012 ) = 1 (127,1012)=1 (127,1012)=1
1 = ( ? 1 ) ? 3 + 4 = ( ? 1 ) ? ( ( ? 30 ) ? 4 + 123 ) + 4 = ( ? 1 ) ? 123 + 31 ? 4 = ( ? 1 ) ? 123 + 31 ? ( ( ? 1 ) ? 123 + 127 ) = ( ? 32 ) ? 123 + 31 ? 127 = ( ? 32 ) ? ( ( ? 7 ) ? 127 + 1012 ) + 31 ? 127 = ( ? 32 ) ? 1012 + 255 ? 127 \begin{array}{rr} 1&=&(-1) \cdot 3&+&4 \\ &=&(-1) \cdot ((-30)\cdot4+123)&+&4 \\ &=&(-1) \cdot 123&+&31\cdot 4 \\ &=&(-1) \cdot 123&+&31\cdot ((-1)\cdot 123+127) \\ &=&(-32) \cdot 123&+&31\cdot127 \\ &=&(-32) \cdot ((-7)\cdot 127+1012)&+&31\cdot127 \\ &=&(-32) \cdot 1012&+&255\cdot127 \\ \end{array} 1?=======?(?1)?3(?1)?((?30)?4+123)(?1)?123(?1)?123(?32)?123(?32)?((?7)?127+1012)(?32)?1012?+++++++?4431?431?((?1)?123+127)31?12731?127255?127?
所以127的逆元是255， x = 255 ? 833 ? m o d ? 1012 = 907. x=255\cdot833\bmod 1012=907. x=255?833mod1012=907.

2. 將同余式方程 23 x ≡ 1 ? m o d ? 140 23 x \equiv 1\bmod140 23x≡1mod140 化為同余式方程組，并用中國剩余定理求解，

{ 23 x ≡ 1 ( ? m o d ? 2 ) 23 x ≡ 1 ( ? m o d ? 2 ) 23 x ≡ 1 ( ? m o d ? 5 ) 23 x ≡ 1 ( ? m o d ? 7 ) \left\{\begin{array}{l}23x \equiv 1(\bmod 2) \\23x \equiv 1(\bmod 2) \\ 23x \equiv 1(\bmod 5) \\ 23x \equiv 1(\bmod 7)\end{array}\right. ????????23x≡1(mod2)23x≡1(mod2)23x≡1(mod5)23x≡1(mod7)? => { x ≡ 1 ( ? m o d ? 2 ) x ≡ 2 ( ? m o d ? 5 ) x ≡ 4 ( ? m o d ? 7 ) \left\{\begin{array}{l}x \equiv 1(\bmod 2) \\ x \equiv 2(\bmod 5) \\ x \equiv 4(\bmod 7)\end{array}\right. ????x≡1(mod2)x≡2(mod5)x≡4(mod7)? M 1 = 35 , M 2 = 28 , M 3 = 20 M_1=35,M_2=28,M_3=20 M1?=35,M2?=28,M3?=20

x = 1 ? 35 ? 1 + 2 ? 28 ? 2 + 4 ? 20 ? 6 ? m o d ? 140 = 627 ? m o d ? 140 = 67 x=1\cdot 35\cdot 1+2\cdot 28\cdot 2+4\cdot 20\cdot 6\bmod 140=627\bmod 140=67 x=1?35?1+2?28?2+4?20?6mod140=627mod140=67

x ≡ 67 ? m o d ? 140 x\equiv 67\bmod 140 x≡67mod140

3. 解同余方程組 { x ≡ 1 ( ? m o d ? 5 ) x ≡ 5 ( ? m o d ? 6 ) x ≡ 4 ( ? m o d ? 7 ) \left\{\begin{array}{l}x \equiv 1(\bmod 5) \\ x \equiv 5(\bmod 6) \\ x \equiv 4(\bmod 7)\end{array}\right. ????x≡1(mod5)x≡5(mod6)x≡4(mod7)?

m = 5 ? 6 ? 7 = 210 , M 1 = 42 , M 2 = 35 , M 3 = 30 m=5\cdot 6\cdot 7=210,M_1=42,M_2=35,M_3=30 m=5?6?7=210,M1?=42,M2?=35,M3?=30

x = 1 ? 42 ? 3 + 5 ? 35 ? 5 + 4 ? 30 ? 4 ? m o d ? 210 = 1481 ? m o d ? 210 = 11 ? m o d ? 210 x=1\cdot 42\cdot 3 + 5\cdot 35\cdot 5 + 4\cdot 30\cdot 4 \bmod 210=1481\bmod 210=11\bmod 210 x=1?42?3+5?35?5+4?30?4mod210=1481mod210=11mod210

x ≡ 11 ? m o d ? 210 x\equiv 11\bmod 210 x≡11mod210

4. 同余方程 x 4 + 7 x + 4 ≡ 0 ( ? m o d ? 3 ) x^{4}+7 x+4 \equiv 0(\bmod 3) x4+7x+4≡0(mod3) 的解為

由歐拉定理 x 2 ≡ 1 ? m o d ? 3 x^2\equiv 1\bmod 3 x2≡1mod3，所以 x 4 ≡ 1 ? m o d ? 3 x^4\equiv 1\bmod 3 x4≡1mod3. 1 + 7 x + 4 ≡ 0 ( ? m o d ? 3 ) 1+7x+4\equiv 0(\bmod 3) 1+7x+4≡0(mod3)

7 x ≡ ? 5 ≡ 1 ( ? m o d ? 3 ) 7x\equiv -5\equiv 1(\bmod 3) 7x≡?5≡1(mod3)，即求解 7 x ≡ 1 ( ? m o d ? 3 ) 7x\equiv 1(\bmod 3) 7x≡1(mod3)，可以列舉一下 0 , 1 , 2 0,1,2 0,1,2，發現只有 x ≡ 1 ? m o d ? 3 x\equiv1\bmod 3 x≡1mod3 成立，

所以解為 x ≡ 1 ( ? m o d ? 3 ) . x\equiv 1 (\bmod 3). x≡1(mod3).

5. (判斷) 同余方程的解數一定不超過同余方程的次數: 錯

參考《資訊安全數學基礎》P109 - 3.3.1 高次同余式的解數

P110 - 例 3.3.1, 四次同余式，有 6 個解，解數超過了次數，