【数検1級対策】中国剰余の定理による連立一次合同式の解法

本記事では,数学検定1級で頻出のトピックについてまとめていきます。

初学者の分かりやすさを優先するため,多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

目次

中国剰余の定理による連立一次合同式の解法

次の連立一次方程式を解け。

(1){x2(mod3)x3(mod5)x2(mod7)

解説

中国剰余定理に従って解きます。解は

(2)x0=i=1kNiuiai

で与えられるため,i=1,2,3に対してNi,ui,aiを求めればよいです。Niについては

(3)N1=57=35,N2=37=21,N3=35=15

となり,aiについては

(4)a1=2,a2=3,a3=2

となります。u1については

(5)35u11(mod3)

を解けばよいです。ユークリッドの互助法を用いてもよいですが,

(6)36u10(mod3)

に注目すると,式(6)から式(5)を引くことにより,

(7)u112(mod3)

が得られます。同様に,

(8)u21(mod5)(9)u31(mod7)

が得られるため,最も簡単な整数として

(10)u1=2,u2=1,u3=1

を選べばよいです。以上より,

(11)x0=3522+2113+1512=23323(mod105)

が得られます。

シェアはこちらからお願いします!

コメント

コメントする

※ Please enter your comments in Japanese to distinguish from spam.

目次