問題概略
10 桁の整数 があります。この について
\begin{align*}
a&=\text{(各位の数の和)}\\
b&=\text{(前から奇数番目の位の数の和)}-\text{(前から偶数番目の位の数の和)}
\end{align*}を計算しました。
を 9 で割ると 6 余り, を 11 で割ると 3 余ったそうです。を 99 で割った余りを求めてください。
解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。
連立合同式
これは連立合同式の問題です。
1 次不定方程式に直す方法と直さない方法の 2 つを解説します。以下,出てくる文字はすべて整数とします。
1 次不定方程式に直す
(1)(2)から , とおけます。ここから を消去すると 1 次不定方程式になります。
これの解(特殊解)を 1 つみつけるとうまく変形できて,一般解を求められます。
(3)のままだと係数が大きすぎて特殊解を探しにくいので, が 3 の倍数であることを利用して とおきます。
この式と を辺ごとに引いて右辺を 0 にします。
3 と 11 は互いに素なので , とおけます。
を に代入するとできあがりです。
求める余りは「69」です。
できるだけ合同式のまま解く
次は極力合同式のまま解く方法を紹介します。
(1)から とおけます。これを(2)に代入します。
以下, で考えます。
\begin{align*}
9k+6\equiv 3&\ \Leftrightarrow\ 9k\equiv -3\\
&\ \Leftrightarrow\ 3k\equiv -1\quad (\because \text{3と11は互いに素})
\end{align*}
4 倍すると の係数が になります。
とおけます。これを に代入するとできあがりです。
こちらの解法の方が余計な文字を増やさなくてすむ分だけ楽だと思います。
高校生くらいだと1次不定方程式を選ぶ人が多いのですが,「係数が法と互いに素なときは割り算ができる」「 の係数を にする」くらいはおぼえておいた方がいいでしょう。