m ∈ Z > 0 m\in {{\mathbb{Z}}_{>0}} m∈Z>0， a i ∈ Z {{a}_{i}}\in \mathbb{Z} ai∈Z， f ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 f\left( x \right)={{a}_{n}}{{x}^{n}}+{{a}_{n-1}}{{x}^{n-1}}+\cdots +{{a}_{1}}x+{{a}_{0}} f(x)=anxn+an−1xn−1+⋯+a1x+a0，称 f ( x ) ≡ 0 ( m o d m ) f\left( x \right)\equiv 0\left( \bmod m \right) f(x)≡0(modm) 为模 m m m的同余式。若 a n ≡ 0 ( m o d m ) {{a}_{n}}\cancel{\equiv }0\left( \bmod m \right) an≡ 0(modm)，则称 n n n为该同余式的次数。
证明
( ⇐ ) \left( \Leftarrow \right) (⇐) a ≡ a ( m o d m ) a\equiv a\left( \bmod m \right) a≡a(modm)，推理是显然的。 ( ⇒ ) \left( \Rightarrow \right) (⇒) ∀ x ≡ a ( m o d m ) , x − a ≡ 0 ( m o d m ) ⇒ m ∣ ( x − a ) ⇒ ∃ k ∈ Z , s . t . \forall x\equiv a\left( \bmod m \right),\text{ }x-a\equiv 0\left( \bmod m \right)\text{ }\Rightarrow \text{ }\left. m \right|\left( x-a \right)\text{ }\Rightarrow \text{ }\exists k\in \mathbb{Z},\text{ }s.t. ∀x≡a(modm), x−a≡0(modm) ⇒ m∣(x−a) ⇒ ∃k∈Z, s.t. x − a = k m ⇔ a = x − k m x-a=km\text{ }\Leftrightarrow \text{ }a=x-km x−a=km ⇔ a=x−km f ( a ) ≡ 0 ⇒ 0 ≡ f ( x − k m ) = a 0 + ∑ j = 1 n a j ( x − k m ) j ≡ a 0 + ∑ j = 1 n ( x − 0 ) j = ∑ j = 0 n a j x j = f ( x ) m o d m \begin{matrix} f\left( a \right)\equiv 0 \\ \begin{aligned} & \Rightarrow 0\equiv f\left( x-km \right)={{a}_{0}}+\sum\limits_{j=1}^{n}{{{a}_{j}}{{\left( x-km \right)}^{j}}} \\ & \equiv {{a}_{0}}+\sum\limits_{j=1}^{n}{{{\left( x-0 \right)}^{j}}}=\sum\limits_{j=0}^{n}{{{a}_{j}}{{x}^{j}}}=f\left( x \right)\text{ }\bmod m \\ \end{aligned} \\ \end{matrix} f(a)≡0⇒0≡f(x−km)=a0+j=1∑naj(x−km)j≡a0+j=1∑n(x−0)j=j=0∑najxj=f(x) modm证明 a x ≡ b ( m o d m ) ⇔ a x − b ≡ 0 ( m o d m ) ⇔ m ∣ ( a x − b ) ⇔ ∃ y ∈ Z , s.t . a x − b = m y ⇔ a x − m y = b \begin{aligned} & \text{ }ax\equiv b\left( \bmod m \right) \\ & \Leftrightarrow ax-b\equiv 0\left( \bmod m \right) \\ & \Leftrightarrow \left. m \right|\left( ax-b \right) \\ & \Leftrightarrow \exists y\in \mathbb{Z},\text{ s}\text{.t}.\text{ }ax-b=my \\ & \Leftrightarrow ax-my=b \\ \end{aligned} ax≡b(modm)⇔ax−b≡0(modm)⇔m∣(ax−b)⇔∃y∈Z, s.t. ax−b=my⇔ax−my=b 而 a x − m y = b ax-my=b ax−my=b有解 ⇔ gcd ( a , − m ) = gcd ( a , m ) ∣ b \Leftrightarrow \gcd \left( a,-m \right)=\left. \gcd \left( a,m \right) \right|b ⇔gcd(a,−m)=gcd(a,m)∣b
解同余式 4 x ≡ 13 m o d 47 4x\equiv 13\text{ }\bmod 47 4x≡13 mod47 解 gcd ( 4 , 47 ) = 1 ∣ 13 \gcd \left( 4,47 \right)=\left. 1 \right|13 gcd(4,47)=1∣13，因此同余式有解。 4 x ≡ 13 m o d 47 ⇔ ( 4 x ⋅ 12 ) ≡ ( 13 × 12 ) = 156 ≡ 15 m o d 47 ⇔ 48 x ≡ 15 m o d 47 ⇔ x ≡ 15 m o d 47 ( ∵ 48 = 47 × 1 + 1 ) \begin{aligned} & 4x\equiv 13\text{ }\bmod 47 \\ & \Leftrightarrow \left( 4x\centerdot 12 \right)\equiv \left( 13\times 12 \right)=156\equiv 15\text{ }\bmod 47 \\ & \Leftrightarrow 48x\equiv 15\text{ }\bmod 47 \\ & \Leftrightarrow x\equiv 15\text{ }\bmod 47\text{ }\left( \because 48=47\times 1+1 \right) \\ \end{aligned} 4x≡13 mod47⇔(4x⋅12)≡(13×12)=156≡15 mod47⇔48x≡15 mod47⇔x≡15 mod47 (∵48=47×1+1)
解同余式 10 x ≡ 6 ( m o d 12 ) 10x\equiv 6\left( \bmod 12 \right) 10x≡6(mod12) 解 10 x ≡ 6 ( m o d 12 ) ⇔ 10 2 x ≡ 6 2 ( m o d 12 2 ) ⇔ 5 x ≡ 3 ( m o d 6 ) \begin{aligned} & \text{ }10x\equiv 6\left( \bmod 12 \right) \\ & \Leftrightarrow \frac{10}{2}x\equiv \frac{6}{2}\left( \bmod \frac{12}{2} \right) \\ & \Leftrightarrow 5x\equiv 3\left( \bmod 6 \right) \\ \end{aligned} 10x≡6(mod12)⇔210x≡26(mod212)⇔5x≡3(mod6) gcd ( 5 , 6 ) = 1 ∣ 3 \gcd \left( 5,6 \right)=\left. 1 \right|3 gcd(5,6)=1∣3，同余式有解。
法一 问题等价于求解 5 x + 6 y = 3 5x+6y=3 5x+6y=3。 观察得 5 x + 6 y = 1 5x+6y=1 5x+6y=1有特解 ( − 1 , 1 ) \left( -1,1 \right) (−1,1) 因此有 5 x + 6 y = 3 5x+6y=3 5x+6y=3有特解 ( − 3 , 3 ) \left( -3,3 \right) (−3,3)，通解是 { x = − 3 − 6 t ≡ − 3 ≡ 3 ( m o d 6 ) y = 3 + 5 t , ∀ t ∈ Z \left\{ \begin{aligned} & x=-3-6t\equiv -3\equiv 3\left( \bmod 6 \right) \\ & y=3+5t \\ \end{aligned} \right.,\text{ }\forall t\in \mathbb{Z} {x=−3−6t≡−3≡3(mod6)y=3+5t, ∀t∈Z
法二 5 x ≡ 3 ( m o d 6 ) ⇔ − x ≡ 3 ( m o d 6 ) ( ∵ 5 ≡ − 1 m o d 6 ) ⇔ x ≡ − 3 ≡ 3 ( m o d 6 ) \begin{aligned} & \text{ }5x\equiv 3\left( \bmod 6 \right) \\ & \Leftrightarrow -x\equiv 3\left( \bmod 6 \right)\text{ }\left( \because 5\equiv -1\text{ }\bmod 6 \right) \\ & \Leftrightarrow x\equiv -3\equiv 3\left( \bmod 6 \right) \\ \end{aligned} 5x≡3(mod6)⇔−x≡3(mod6) (∵5≡−1 mod6)⇔x≡−3≡3(mod6)
注 x ≡ 3 ( m o d 6 ) x\equiv 3\left( \bmod 6 \right) x≡3(mod6)也可以写成以下形式 x ≡ 3 , 9 ( m o d 12 ) x\equiv 3,9\left( \bmod 12 \right) x≡3,9(mod12)
解同余式 10 x ≡ 6 ( m o d 14 ) 10x\equiv 6\left( \bmod 14 \right) 10x≡6(mod14) 解 10 x ≡ 6 ( m o d 14 ) ⇔ 10 2 x ≡ 6 2 ( m o d 14 2 ) ⇔ 5 x ≡ 3 ( m o d 7 ) \begin{aligned} & \text{ }10x\equiv 6\left( \bmod 14 \right) \\ & \Leftrightarrow \frac{10}{2}x\equiv \frac{6}{2}\left( \bmod \frac{14}{2} \right) \\ & \Leftrightarrow 5x\equiv 3\left( \bmod 7 \right) \\ \end{aligned} 10x≡6(mod14)⇔210x≡26(mod214)⇔5x≡3(mod7) gcd ( 5 , 7 ) = 1 ∣ 3 \gcd \left( 5,7 \right)=\left. 1 \right|3 gcd(5,7)=1∣3，因此同余式有解。 5 x ≡ 3 ( m o d 7 ) ⇔ 5 x + 0 ≡ 3 + 7 ( m o d 7 ) ⇔ 5 x ≡ 10 ( m o d 7 ) ⇔ x ≡ 2 ( m o d 7 ) ( ∵ gcd ( 5 , 7 ) = 1 ) \begin{aligned} & \text{ }5x\equiv 3\left( \bmod 7 \right) \\ & \Leftrightarrow 5x+0\equiv 3+7\left( \bmod 7 \right) \\ & \Leftrightarrow 5x\equiv 10\left( \bmod 7 \right) \\ & \Leftrightarrow x\equiv 2\left( \bmod 7 \right)\text{ }\left( \because \gcd \left( 5,7 \right)=1 \right) \\ \end{aligned} 5x≡3(mod7)⇔5x+0≡3+7(mod7)⇔5x≡10(mod7)⇔x≡2(mod7) (∵gcd(5,7)=1)
解同余式 256 x ≡ 179 ( m o d 337 ) 256x\equiv 179\left( \bmod 337 \right) 256x≡179(mod337) 法一 256 x ≡ 179 ( m o d 337 ) ⇔ ( 256 − 337 ) x = − 81 x ≡ 179 ( m o d 337 ) \begin{aligned} & \text{ }256x\equiv 179\left( \bmod 337 \right) \\ & \Leftrightarrow \left( 256-337 \right)x=-81x\equiv 179\left( \bmod 337 \right) \\ \end{aligned} 256x≡179(mod337)⇔(256−337)x=−81x≡179(mod337) 问题等价于求解不定方程 − 81 x + 337 y = 179 -81x+337y=179 −81x+337y=179的解。 337 = 81 × 4 + 13 81 = 13 × 6 + 3 13 = 3 × 4 + 1 \begin{aligned} & 337=81\times 4+13 \\ & 81=13\times 6+3 \\ & 13=3\times 4+1 \\ \end{aligned} 337=81×4+1381=13×6+313=3×4+1 gcd ( − 81 , 337 ) = 1 ∣ 179 \gcd \left( -81,337 \right)=\left. 1 \right|179 gcd(−81,337)=1∣179，不定方程有解。 P 0 = 1 , P 1 = 4 , P 2 = 6 × 4 + 1 = 25 , P 3 = 4 × 25 + 4 = 104 Q 0 = 0 , Q 1 = 1 , Q 2 = 6 , Q 3 = 4 × 6 + 1 = 25 \begin{aligned} & {{P}_{0}}=1,\text{ }{{P}_{1}}=4,\text{ }{{P}_{2}}=6\times 4+1=25,\text{ }{{P}_{3}}=4\times 25+4=104 \\ & {{Q}_{0}}=0,\text{ }{{Q}_{1}}=1,\text{ }{{Q}_{2}}=6,\text{ }{{Q}_{3}}=4\times 6+1=25 \\ \end{aligned} P0=1, P1=4, P2=6×4+1=25, P3=4×25+4=104Q0=0, Q1=1, Q2=6, Q3=4×6+1=25 因此 − 81 x + 337 y = 1 -81x+337y=1 −81x+337y=1有特解 ( ( − 1 ) 3 + 1 P 3 , ( − 1 ) 3 − 1 Q 3 ) = ( 104 , 25 ) \left( {{\left( -1 \right)}^{3+1}}{{P}_{3}},{{\left( -1 \right)}^{3-1}}{{Q}_{3}} \right)=\left( 104,25 \right) ((−1)3+1P3,(−1)3−1Q3)=(104,25) − 81 x + 337 y = 179 -81x+337y=179 −81x+337y=179有通解 { x = 104 × 179 − 337 t y = 25 × 179 − 81 t , ∀ t ∈ Z \left\{ \begin{aligned} & x=104\times 179-337t \\ & y=25\times 179-81t \\ \end{aligned} \right.,\text{ }\forall t\in \mathbb{Z} {x=104×179−337ty=25×179−81t, ∀t∈Z 因此同余式 256 x ≡ 179 ( m o d 337 ) 256x\equiv 179\left( \bmod 337 \right) 256x≡179(mod337)的解是 x ≡ 104 × 179 ≡ 104 × ( − 158 ) ( ∵ 179 − 337 = 158 ) = ( 2 3 × 13 ) × ( − 2 × 79 ) = ( − 2 4 ) × ( 13 × 79 ) ≡ ( − 16 ) × 16 ( ∵ 13 × 79 = 1027 = 337 × 3 + 16 ) = − 256 ≡ 81 ( − 256 = − 337 × 1 + 81 ) m o d 337 \begin{aligned} & x\equiv 104\times 179 \\ & \equiv 104\times \left( -158 \right)\text{ }\left( \because 179-337=158 \right) \\ & =\left( {{2}^{3}}\times 13 \right)\times \left( -2\times 79 \right) \\ & =\left( -{{2}^{4}} \right)\times \left( 13\times 79 \right) \\ & \equiv \left( -16 \right)\times 16\text{ }\left( \because 13\times 79=1027=337\times 3+16 \right) \\ & =-256 \\ & \equiv 81\text{ }\left( -256=-337\times 1+81 \right) \\ & \bmod 337 \\ \end{aligned} x≡104×179≡104×(−158) (∵179−337=158)=(23×13)×(−2×79)=(−24)×(13×79)≡(−16)×16 (∵13×79=1027=337×3+16)=−256≡81 (−256=−337×1+81)mod337
法二 256 x ≡ 179 ( m o d 337 ) ⇔ 256 x ≡ ( 179 + 337 ) = 516 ( m o d 337 ) ⇔ 256 4 x = 64 x ≡ 516 4 = 129 ( m o d 337 ) ( ∵ gcd ( 2 , 337 ) = 1 ⇒ gcd ( 2 2 = 4 , 337 ) = 1 ) ⇔ 64 x ≡ ( 129 − 337 ) = − 208 ( m o d 337 ) ⇔ 64 16 x = 4 x ≡ − 208 16 = − 13 ( m o d 337 ) ( ∵ gcd ( 2 , 337 ) = 1 ⇒ gcd ( 2 4 = 16 , 337 ) = 1 ) ⇔ 4 x ≡ ( − 13 + 337 ) = 324 ( m o d 337 ) ⇔ x ≡ 81 ( m o d 337 ) \begin{aligned} & \text{ }256x\equiv 179\left( \bmod 337 \right) \\ & \Leftrightarrow 256x\equiv \left( 179+337 \right)=516\left( \bmod 337 \right) \\ & \Leftrightarrow \frac{256}{4}x=64x\equiv \frac{516}{4}=129\left( \bmod 337 \right)\text{ }\left( \begin{aligned} & \because \gcd \left( 2,337 \right)=1\text{ } \\ & \Rightarrow \text{ }\gcd \left( {{2}^{2}}=4,337 \right)=1 \\ \end{aligned} \right) \\ & \Leftrightarrow 64x\equiv \left( 129-337 \right)=-208\left( \bmod 337 \right) \\ & \Leftrightarrow \frac{64}{16}x=4x\equiv \frac{-208}{16}=-13\left( \bmod 337 \right)\text{ }\left( \begin{aligned} & \because \gcd \left( 2,337 \right)=1\text{ } \\ & \Rightarrow \text{ }\gcd \left( {{2}^{4}}=16,337 \right)=1 \\ \end{aligned} \right) \\ & \Leftrightarrow 4x\equiv \left( -13+337 \right)=324\left( \bmod 337 \right) \\ & \Leftrightarrow x\equiv 81\left( \bmod 337 \right) \\ \end{aligned} 256x≡179(mod337)⇔256x≡(179+337)=516(mod337)⇔4256x=64x≡4516=129(mod337) (∵gcd(2,337)=1 ⇒ gcd(22=4,337)=1)⇔64x≡(129−337)=−208(mod337)⇔1664x=4x≡16−208=−13(mod337) (∵gcd(2,337)=1 ⇒ gcd(24=16,337)=1)⇔4x≡(−13+337)=324(mod337)⇔x≡81(mod337)
解同余式 1215 x ≡ 560 ( m o d 2755 ) 1215x\equiv 560\left( \bmod 2755 \right) 1215x≡560(mod2755) 解 1215 x ≡ 560 ( m o d 2755 ) ⇔ 1215 5 x = 243 x ≡ 560 5 = 112 ( m o d 2755 5 = 551 ) ⇔ 243 x ≡ ( 112 + 551 ) = 663 ( m o d 551 ) ⇔ 243 3 x = 81 x ≡ 663 3 = 221 ( m o d 551 ) ( ∵ gcd ( 3 , 551 ) = 1 ) ⇔ 81 x ≡ ( 221 − 551 ) = − 330 ( m o d 551 ) ⇔ 81 3 x = 27 x ≡ − 330 3 = − 110 ( m o d 551 ) ⇔ 27 x ≡ ( − 110 + 551 ) = 441 ( m o d 551 ) ⇔ 27 3 x = 9 x ≡ 441 3 = 147 ( m o d 551 ) ⇔ 9 3 x = 3 x ≡ 147 3 = 49 ( m o d 551 ) ⇔ 3 x ≡ ( 49 + 551 ) = 600 ( m o d 551 ) ⇔ x ≡ 200 ( m o d 551 ) \begin{aligned} & \text{ }1215x\equiv 560\left( \bmod 2755 \right) \\ & \Leftrightarrow \frac{1215}{5}x=243x\equiv \frac{560}{5}=112\left( \bmod \frac{2755}{5}=551 \right) \\ & \Leftrightarrow 243x\equiv \left( 112+551 \right)=663\left( \bmod 551 \right) \\ & \Leftrightarrow \frac{243}{3}x=81x\equiv \frac{663}{3}=221\left( \bmod 551 \right)\text{ }\left( \because \gcd \left( 3,551 \right)=1 \right) \\ & \Leftrightarrow 81x\equiv \left( 221-551 \right)=-330\left( \bmod 551 \right) \\ & \Leftrightarrow \frac{81}{3}x=27x\equiv \frac{-330}{3}=-110\left( \bmod 551 \right) \\ & \Leftrightarrow 27x\equiv \left( -110+551 \right)=441\left( \bmod 551 \right) \\ & \Leftrightarrow \frac{27}{3}x=9x\equiv \frac{441}{3}=147\left( \bmod 551 \right) \\ & \Leftrightarrow \frac{9}{3}x=3x\equiv \frac{147}{3}=49\left( \bmod 551 \right) \\ & \Leftrightarrow 3x\equiv \left( 49+551 \right)=600\left( \bmod 551 \right) \\ & \Leftrightarrow x\equiv 200\left( \bmod 551 \right) \\ \end{aligned} 1215x≡560(mod2755)⇔51215x=243x≡5560=112(mod52755=551)⇔243x≡(112+551)=663(mod551)⇔3243x=81x≡3663=221(mod551) (∵gcd(3,551)=1)⇔81x≡(221−551)=−330(mod551)⇔381x=27x≡3−330=−110(mod551)⇔27x≡(−110+551)=441(mod551)⇔327x=9x≡3441=147(mod551)⇔39x=3x≡3147=49(mod551)⇔3x≡(49+551)=600(mod551)⇔x≡200(mod551)
解同余式 1296 x ≡ 1125 ( m o d 1935 ) 1296x\equiv 1125\left( \bmod 1935 \right) 1296x≡1125(mod1935) 解 1296 x ≡ 1125 ( m o d 1935 ) ⇔ 1296 3 = 432 x ≡ 1125 3 = 375 ( m o d 1935 3 = 645 ) ⇔ 432 3 x = 144 x ≡ 375 3 = 125 ( m o d 645 3 = 215 ) ⇔ 144 x ≡ ( 125 − 215 ) = − 90 ( m o d 215 ) ⇔ 144 3 x = 48 x ≡ − 90 3 = − 30 ( m o d 215 ) ( ∵ gcd ( 3 , 215 ) = 1 ) ⇔ 48 3 x = 16 x ≡ − 30 3 = − 10 ( m o d 215 ) ⇔ 16 2 x = 8 x ≡ − 10 2 = − 5 ( m o d 215 ) ( ∵ gcd ( 2 , 215 ) = 1 ) ⇔ 8 x ≡ ( − 5 + 215 ) = 210 ( m o d 215 ) ⇔ 8 2 x = 4 x ≡ 210 2 = 105 ( m o d 215 ) ⇔ 4 x ≡ ( 105 + 215 ) = 320 ( m o d 215 ) ⇔ x ≡ 80 ( m o d 215 ) \begin{aligned} & \text{ }1296x\equiv 1125\left( \bmod 1935 \right) \\ & \Leftrightarrow \frac{1296}{3}=432x\equiv \frac{1125}{3}=375\left( \bmod \frac{1935}{3}=645 \right) \\ & \Leftrightarrow \frac{432}{3}x=144x\equiv \frac{375}{3}=125\left( \bmod \frac{645}{3}=215 \right) \\ & \Leftrightarrow 144x\equiv \left( 125-215 \right)=-90\left( \bmod 215 \right) \\ & \Leftrightarrow \frac{144}{3}x=48x\equiv \frac{-90}{3}=-30\left( \bmod 215 \right)\text{ }\left( \because \gcd \left( 3,215 \right)=1 \right) \\ & \Leftrightarrow \frac{48}{3}x=16x\equiv \frac{-30}{3}=-10\left( \bmod 215 \right) \\ & \Leftrightarrow \frac{16}{2}x=8x\equiv \frac{-10}{2}=-5\left( \bmod 215 \right)\text{ }\left( \because \gcd \left( 2,215 \right)=1 \right) \\ & \Leftrightarrow 8x\equiv \left( -5+215 \right)=210\left( \bmod 215 \right) \\ & \Leftrightarrow \frac{8}{2}x=4x\equiv \frac{210}{2}=105\left( \bmod 215 \right) \\ & \Leftrightarrow 4x\equiv \left( 105+215 \right)=320\left( \bmod 215 \right) \\ & \Leftrightarrow x\equiv 80\left( \bmod 215 \right) \\ \end{aligned} 1296x≡1125(mod1935)⇔31296=432x≡31125=375(mod31935=645)⇔3432x=144x≡3375=125(mod3645=215)⇔144x≡(125−215)=−90(mod215)⇔3144x=48x≡3−90=−30(mod215) (∵gcd(3,215)=1)⇔348x=16x≡3−30=−10(mod215)⇔216x=8x≡2−10=−5(mod215) (∵gcd(2,215)=1)⇔8x≡(−5+215)=210(mod215)⇔28x=4x≡2210=105(mod215)⇔4x≡(105+215)=320(mod215)⇔x≡80(mod215)
求联立同余式 { x + 4 y − 29 ≡ 0 ( m o d 143 ) ( 1 ) 2 x − 9 y + 84 ≡ 0 ( m o d 143 ) ( 2 ) \left\{ \begin{aligned} & x+4y-29\equiv 0\left( \bmod 143 \right)\text{ }\left( 1 \right) \\ & 2x-9y+84\equiv 0\left( \bmod 143 \right)\text{ }\left( 2 \right) \\ \end{aligned} \right. {x+4y−29≡0(mod143) (1)2x−9y+84≡0(mod143) (2) 的解。 解 ( 1 ) × 2 − ( 2 ) ⇒ 17 y − 142 ≡ 0 ( m o d 143 ) ⇒ 17 y ≡ 142 ≡ − 1 ( m o d 143 ) \left( 1 \right)\times 2-\left( 2 \right)\text{ }\Rightarrow \text{ }17y-142\equiv 0\left( \bmod 143 \right)\text{ }\Rightarrow 17y\equiv 142\equiv -1\left( \bmod 143 \right) (1)×2−(2) ⇒ 17y−142≡0(mod143) ⇒17y≡142≡−1(mod143) gcd ( 11 , 17 ) = 1 , gcd ( 13 , 17 ) = 1 \gcd \left( 11,17 \right)=1,\text{ }\gcd \left( 13,17 \right)=1 gcd(11,17)=1, gcd(13,17)=1，由欧拉定理有 17 φ ( 11 ) = 17 10 ≡ 1 ( m o d 11 ) ⇒ ( 1 7 10 ) 6 = 17 60 ≡ 1 ( m o d 11 ) 17 φ ( 13 ) = 17 12 ≡ 1 ( m o d 13 ) ⇒ ( 17 12 ) 5 = 17 60 ≡ 1 ( m o d 13 ) } ⇒ 1 7 60 ≡ 1 mod ( l c m ( 11 , 13 ) = 143 ) \begin{aligned} & \left. \begin{aligned} & {{17}^{\varphi \left( 11 \right)}}={{17}^{10}}\equiv 1\left( \bmod 11 \right)\text{ }\Rightarrow \text{ }{{\left( \text{1}{{\text{7}}^{10}} \right)}^{6}}\text{=}{{17}^{60}}\equiv 1\left( \bmod 11 \right) \\ & {{17}^{\varphi \left( 13 \right)}}={{17}^{12}}\equiv 1\left( \bmod 13 \right)\text{ }\Rightarrow \text{ }{{\left( {{17}^{12}} \right)}^{5}}={{17}^{60}}\equiv 1\left( \bmod 13 \right) \\ \end{aligned} \right\} \\ & \Rightarrow \text{ 1}{{\text{7}}^{60}}\equiv 1\text{ mod}\left( lcm\left( 11,13 \right)=143 \right) \\ \end{aligned} 17φ(11)=1710≡1(mod11) ⇒ (1710)6=1760≡1(mod11)17φ(13)=1712≡1(mod13) ⇒ (1712)5=1760≡1(mod13)⎭⎬⎫⇒ 1760≡1 mod(lcm(11,13)=143) 因此有 y = 1 ⋅ y ≡ 17 60 ⋅ y = ( 17 y ) ⋅ 17 59 ≡ − 17 59 ( ∵ 17 y ≡ − 1 ( m o d 143 ) ) = − 17 × ( 17 2 ) 29 ≡ − 17 × 3 29 ( ∵ 17 2 = 289 = 143 × 2 + 3 ) = ( − 17 × 3 ) × 3 28 = − 51 × ( 3 4 ) 7 = − 51 × 81 7 = ( − 51 × 81 ) × ( 81 2 ) 3 ≡ ( 51 × 62 ) × ( 62 2 ) 3 ≡ 16 × ( 126 ) 3 ( ∵ 51 × 62 = 3162 = 143 × 22 + 16 62 2 = 3844 = 143 × 26 + 126 ) ≡ 16 × ( − 17 ) 3 = ( − 16 × 17 ) × 17 2 ≡ 14 × 3 ( ∵ − 16 × 17 = − 272 = 143 × ( − 2 ) + 14 17 2 = 289 = 143 × 2 + 3 ) = 42 ( m o d 143 ) \begin{aligned} & y=1\centerdot y\equiv {{17}^{60}}\centerdot y=\left( 17y \right)\centerdot {{17}^{59}} \\ & \equiv -{{17}^{59}}\text{ }\left( \because 17y\equiv -1\left( \bmod 143 \right) \right) \\ & =-17\times {{\left( {{17}^{2}} \right)}^{29}} \\ & \equiv -17\times {{3}^{29}}\text{ }\left( \because {{17}^{2}}=289=143\times 2+3 \right) \\ & =\left( -17\times 3 \right)\times {{3}^{28}} \\ & =-51\times {{\left( {{3}^{4}} \right)}^{7}} \\ & =-51\times {{81}^{7}} \\ & =\left( -51\times 81 \right)\times {{\left( {{81}^{2}} \right)}^{3}} \\ & \equiv \left( 51\times 62 \right)\times {{\left( {{62}^{2}} \right)}^{3}} \\ & \equiv 16\times {{\left( 126 \right)}^{3}}\text{ }\left( \begin{aligned} & \because 51\times 62=3162=143\times 22+16 \\ & {{62}^{2}}=3844=143\times 26+126 \\ \end{aligned} \right) \\ & \equiv 16\times {{\left( -17 \right)}^{3}} \\ & =\left( -16\times 17 \right)\times {{17}^{2}} \\ & \equiv 14\times 3\text{ }\left( \begin{aligned} & \because -16\times 17=-272=143\times \left( -2 \right)+14 \\ & {{17}^{2}}=289=143\times 2+3 \\ \end{aligned} \right) \\ & =42\left( \bmod 143 \right) \\ \end{aligned} y=1⋅y≡1760⋅y=(17y)⋅1759≡−1759 (∵17y≡−1(mod143))=−17×(172)29≡−17×329 (∵172=289=143×2+3)=(−17×3)×328=−51×(34)7=−51×817=(−51×81)×(812)3≡(51×62)×(622)3≡16×(126)3 (∵51×62=3162=143×22+16622=3844=143×26+126)≡16×(−17)3=(−16×17)×172≡14×3 (∵−16×17=−272=143×(−2)+14172=289=143×2+3)=42(mod143) 因此有 4 y ≡ 4 × 42 = 168 ≡ 25 ( m o d 143 ) ⇒ x + 4 y − 29 ≡ x + 25 − 29 = x − 4 ≡ 0 ( m o d 143 ) ⇒ x ≡ 4 ( m o d 143 ) \begin{aligned} & 4y\equiv 4\times 42=168\equiv 25\left( \bmod 143 \right) \\ & \Rightarrow x+4y-29\equiv x+25-29=x-4\equiv 0\left( \bmod 143 \right) \\ & \Rightarrow x\equiv 4\left( \bmod 143 \right) \\ \end{aligned} 4y≡4×42=168≡25(mod143)⇒x+4y−29≡x+25−29=x−4≡0(mod143)⇒x≡4(mod143) 因此该同余式组的解为 { x ≡ 4 ( m o d 143 ) y ≡ 42 ( m o d 143 ) \left\{ \begin{aligned} & x\equiv 4\left( \bmod 143 \right) \\ & y\equiv 42\left( \bmod 143 \right) \\ \end{aligned} \right. {x≡4(mod143)y≡42(mod143)
