3で割ると1余り,\ 5で割ると3余り,\ 7で割ると4余る自然数$N$のうち,\ 最小のもの
を求めよ. 中国剰余定理と百五減算{a,\ b,\ cをどの2つも互いに素}な自然数とする.$
$aで割るとr_1\,余り,\ bで割るとr_2\,余り,\ cで割るとr_3\,余る自然数Nは,$
$1≦ N≦ abcを1周期とするとき,\ 1周期の中にただ1つ存在する.{不定方程式$ax+by=c}$を解く\,
3と5は互いに素であるから $
中国剰余定理を知識としてもっていると問題の見通しがよくなることがある.
3個の自然数の場合を示したが,\ 2個の自然数や4個以上の自然数の場合も同様に成り立つ.
2個の自然数の場合の中国剰余定理の証明を本項の最後に示しておく.
中国剰余定理は,\ 具体的に考えるとほぼ当たり前の定理に感じられるだろう.
自然数を並べたとき,\ 3で割るとr_1\,余る自然数は周期3で現れる.
同様に,\ 5で割るとr_2\,余る自然数は周期5で,\ 7で割るとr_3\,余る自然数は周期7で現れる.
よって,\ 3で割るとr_1,\ 5で割るとr_2,\ 7で割るとr_3\,余る自然数Nは3･5･7=105の周期で現れる.
また,\ r_1\,はr_1=0\,～\,2の3通り,\ r_2\,はr_2=0\,～\,4の5通り,\ r_3\,はr_3=0\,～\,6の7通りである.
よって,\ 異なる(r_1,\ r_2,\ r_3)のパターンは3･5･7=105通りある.
全部で105通りあって周期105なのであるから,\ 1周期内に条件を満たすNがただ1つ存在する.}
条件を文字を用いて数式で表現し,\ 不定方程式ax+by=cに帰着させる}のが標準解法である.
結局,\ 3x+1=5y+3かつ5y+3=7z+4を満たすようなNの条件を考える}ことになる.
ax+by=c型の不定方程式については習得済みを前提とするが,\ 一応その扱いを軽く確認する.
特殊解(x,\ y)=(α, β)を見つけると,\ a(x-α)=-\,b(y-β)と変形できる.
a,\ bが互いに素のときx-α\,が-bの倍数,\ y-β\,がaの倍数より x-α=-\,bk,\ y-β=ak
まず,\ 一方の不定方程式を解く.
その解を2つ目の不定方程式に代入した後,\ それを解く.
さらにその解を最初の式に代入すると,\ Nが105で割ると88余る数であることがわかる.
3で割ると1余り,\ 5で割ると3余る自然数Nは,\ 以下のように考えると楽に求められる.
Nを3,\ 5で割ったときの余り1,\ 3は,\ いずれも割る数3,\ 5より2小さい.
よって,\ N+2は3で割っても5で割っても割り切れるから,\ 15の倍数}である.
ゆえに N+2=15k\ より N=15k-2\ (k:整数)
これは,\ N=5y+3=5(3k-1)+3=15k-2と一致する.
M=70r_1+21r_2+15r_3\ (r_1,\ r_2,\ r_3:整数)}$という数を考える.
$M=69r_1+21r_2+15r_3+r_1=3(23r_1+7r_2+5r_3)+r_1$
参考までに百五減算(3,\ 5,\ 7で割ったときの余りから元の数を求める和算)による別解も示した.
70r_1+21r_2+15r_3\,を求め,\ 105以下の整数になるまで105を繰り返し引く}とNが求まる.
Mは,\ (r_1,\ r_2,\ r_3)の代入のみで条件を満たす自然数の1つを求められる特別な数なのである.
なお,\ 記述試験で中国剰余定理を無断使用してよいかは微妙である.
特別な数Mがどのようにして導かれるのかを合同式を用いて解説する.
M≡ r_1±od3,\ M≡ r_2±od5,\ M≡ r_3±od7}
これを満たすMを(r_1,\ r_2,\ r_3)を用いて1つの式で表せられれば,\ 余りから簡単に元の数が求まる.
3,\ 5,\ 7について対称性をもつ数\については話が早いのだが,\ 問題はmod}\,3である.
仮にM=35r_1+21r_2+15r_3\,とすると,\ 35≡2のせいでM≡2r_1±od3となってしまう.
そこで,\ 35の倍数(5でも7でも割り切れる数)かつ3で割ると1余る数を考える}と,\ 70がある.
M=70r_1+21r_2+15r_3\,とすることにより,\ M≡ 70r_1≡ r_1±od3}となるわけである.
原理の理解があれば,\ 割る数が3,\ 5,\ 7以外の場合でも自分で特別な数Mを作り出すことができる.
105より小さい自然数$N$を3,\ 5,\ 7で割ったときの余りをそれぞれ$r_1,\ r_2,\ r_3$とする.
$70r_1+21r_2+15r_3$を105で割ったときの余りが$N$に等しいことを示せ. \\
$N$は105より小さい自然数であるから,\ 105で割ったときの余りは$N}$}である.
{2個の自然数の場合の中国剰余定理の証明a,\ bを互いに素}な自然数とする.$
$
N≡ r_1±od a
N≡ r_2±od b
-.5zw}を満たす整数Nが,\ abを法として一意に存在する.$
解の存在性}\,]
$a,\ b$が互いに素であるから,\ $as+bt=1$を満たす整数$s,\ t$が存在する.}
[\,解の一意性}\,]
中国剰余定理を合同式で表現すると上のようになる.
「\,abを法として一意に存在する」とは,\ 「\,abで割ったときの余りが等しい」ということである.
このような整数は周期abで存在する.
つまり,\ 1≦ N≦ abを1周期とするとき,\ 1周期の中にただ1つ存在することを意味する.
合同式を用いて簡潔に証明する.\ 受験での重要度は低いが,\ 上級者は確認しておくことを推奨する.
次の整数分野の最重要定理を利用する(証明は別項).
a,\ bが互いに素\ ⇔\ ax+by=1を満たす整数x,\ yが存在する}
証明を理解するには,\ 一旦具体的な整数で考えてみるとよい.\ \ a=3,\ b=5の場合を示しておく.
3,\ 5は互いに素であるから,\ 3s+5t=1を満たす整数s,\ tが存在する.
N=r_1bt+r_2asは,\ 先程の百五減算における特別な数Mのことである.
5x+3yという数を考える.
5の倍数で3で割ると1余る数には10がある(\,t=2のとき5t≡ 1±od3が成り立つ).
3の倍数で5で割ると1余る数には6がある\ \ (\,s=2のとき3s≡1±od5が成り立つ).
一意性の証明は,\ 別の文字で設定して一致することを示す}という手法を用いている.
abで割ったときの余りが等しい,\ つまりN_1≡ N_2±od{ab}を示せばよい.
N_1-N_2\,がaで割ってもbで割っても割りきれる数(aの倍数かつbの倍数)であるとわかる.
a,\ bは互いに素なので,\ N_1-N_2\,はabの倍数といえる.
