HEAVEN INSITE's Blog

　こんばんは。モジュラス攻略月間開催中です。でも今はあえて『真田丸』観ます。

モジュラス
まずはルールのおさらい。

X≡A (mod B)

これは、ある数をBで割ると、あまりはAという意味。
≡のマークは余りが同じである事を表す。

よって
X＝B×m＋A（mは整数）

例題１
x≡3(mod19)かつx≡2(mod11)を満たす整数xをすべて求めよ。

x＝19m＋3 …①（mは整数）
x＝11n＋2 …②（nは整数）

①を②に代入して
19m＋3＝11n＋2

移項して

19m＝11n－1…③

左辺は19の倍数なので19、38・・・76（m＝４）
右辺は11の倍数なので11、22・・・77（n＝７）

m＝４、n＝７　がとりあえず答えの一つとして該当する。

よって
19×（４）＝11×（７）－１

なので
19(m－４)＝11(n－７)－1－（－1）

19(m－４)＝11(n－７)
となる。

さらに19と11は互いに素である（同時に割る数が１しかない）から、この等式を成り立たせるためには

m－4も11の倍数（nー7は19の倍数）だということになる。

したがって
m－4＝11k

移項して

m＝11k＋4（kは整数）…④

最後に④を①に代入して

x＝19m＋3
x＝19(11k＋4)＋3

したがってx≡3(mod19)かつx≡2(mod11)を満たす整数xは

x＝209k＋79（kは任意の整数）

例題２
x≡3(mod23)かつx≡2(mod14)を満たす整数xをすべて求めよ。

x＝23m＋3 …①（mは整数）
x＝14n＋2 …②（nは整数）

①を②に代入して
23m＋3＝14n＋2

移項して

23m＝14n－1…③

左辺は23の倍数なので23、46・・・69（m＝３）
右辺は14の倍数なので14、28・・・70（n＝５）

m＝３、n＝５　がとりあえず答えの一つとして該当する。

よって
23×（３）＝14×（５）－１

なので
23(m－３)＝14(n－５)－1－（－1）

23(m－３)＝14(n－５)
となる。

さらに23と14は互いに素である（同時に割る数が１しかない）から

m－３も14の倍数。

したがって
m－３＝14k

移項して

m＝14k＋３（kは整数）…④

最後に④を①に代入して

x＝23m＋3
x＝23(14k＋３)＋3

したがってx≡3(mod19)かつx≡2(mod11)を満たす整数xは

x＝322k＋72（kは任意の整数）

例題３
x≡４(mod23)かつx≡２(mod14)を満たす整数xをすべて求めよ。

x＝23m＋４（mは整数）…①
x＝14n＋２（nは整数）…②

①を②に代入して
23m＋４＝14n＋２

23m＝14n－２…③

左辺は23の倍数なので23、46、69…138（m＝6）
右辺は14の倍数なので14、28、42…140（n＝10）

m＝６、n＝10　がとりあえず該当する。

よって
23×（６）＝14×（10）－２

なので
23(m－６)＝14(n－10)－２－（－２）

23(m－６)＝14(n－10)
となる。

さらに23と14は互いに素である（同時に割る数が１しかない）から

m－６も14の倍数。

したがって
m－６＝14k

移項して
m＝14k＋６

m＝14k＋６（kは整数）…④

最後に④を①に代入して
x＝23m+４
x＝23(14k＋６)+4
x＝322k＋142

したがってx≡2(mod23)かつx≡３(mod14)を満たす整数xは

x＝322k＋142（kは任意の整数）