【応用】合同式を使って余りを求める
ここでは、合同式を使って、いろいろな余りを求める問題を見ていきます。
合同式を使って余りを求めるその1
【応用】合同式で見たように、合同式を使えば余りを簡単に調べることができます。このとき、使える内容をもう一度まとめておきましょう。
- $a+b \equiv c+d \pmod m$
- $a-b \equiv c-d \pmod m$
- $ab \equiv cd \pmod m$
- $a^k \equiv c^k \pmod m$
これより、和・差・積・べき乗を、合同なわかりやすい数に置き換えて考えることができます。3の倍数であることを示すには、 $3$ を法として $0$ と合同であることを示せばいいですね。
$n\equiv 0 \pmod 3$ のときは、\[ 2n^3+3n^2+n \equiv 0+0+0 \equiv 0 \pmod 3 \]なので、3の倍数です。
$n\equiv 1 \pmod 3$ のときは、\[ 2n^3+3n^2+n \equiv 2+3+1 \equiv 0 \pmod 3 \]なので、3の倍数です。
$n\equiv 2 \pmod 3$ のときは、\[ 2n^3+3n^2+n \equiv 16+12+2 \equiv 30 \equiv 0 \pmod 3 \]なので、3の倍数です。
こうして、3の倍数であることがわかります。これで示せました。
また、同じようにすれば2の倍数となることも示すことができ、6の倍数になることがわかります。
なお、この式を因数分解すると\[ n(n+1)(2n+1) \]となります。これは、【標準】連続する整数の積の後半で見た問題と同じです。リンク先では、連続する整数の積を見つける方法、場合分けをして地道に計算する方法の2つで解いています。合同式を使う方法は、この場合分けの方法に対応していますが、この問題の場合は、まだ合同式を使うメリットはまだそんなに大きくありません。
合同式を使って余りを求めるその2
【応用】合同式の最後で見た内容とほぼ同じです。 $17$ を法としたときに、 $1$ や $-1$ と合同となるような $2^k$ を探すようにします。
計算していくと、しばらく見つかりませんが、頑張って続けると\[ 2^8=256=17\times15+1 \]にたどりつけます。これより、
\begin{eqnarray}
2^{100}
& \equiv &
2^4\times (2^8)^{12} \pmod {17} \\[5pt]
& \equiv &
16\times 1^{12} \pmod {17} \\[5pt]
& \equiv &
16 \pmod {17} \\[5pt]
\end{eqnarray}となることがわかり、余りは16となります。
ところで、 $2^8=17\times 15+1$ が見つかったからよかったものの、見つからなかったら大変です。実は、こういう数が見つかるための条件は知られているのですが、それはまた別の機会で見ることにします。
合同式を使って余りを求めるその3
例えば、 $n=1$ なら、 $2^3+3^3=35$ で、 $n=2$ なら、 $2^4+3^5=259$ となり、たしかに7の倍数です。しかし、直接示すのは難しそうですね。
$2^{n+2}$ は、 $2^n\times 2^2$ なので、 $4\times 2^n$ のことです。また、2項目は\[ 3^{2n+1}=3^{2n}\times 3^1=3\times 9^n \]となります。ここで、 $7$ を法として考えると、 $9\equiv 2$ となるので、 $9^n\equiv 2^n$ とできます。よって、うまく計算できそうだ、という見通しが立ちます。
\begin{eqnarray}
2^{n+2}+3^{2n+1}
& \equiv &
4\times 2^n+3\times 9^n \pmod 7 \\[5pt]
& \equiv &
4\times 2^n+3\times 2^n \pmod 7 \\[5pt]
& \equiv &
7\times 2^n \pmod 7 \\[5pt]
& \equiv &
0 \pmod 7 \\[5pt]
\end{eqnarray}となり、7の倍数になることがわかります。
合同式を使い、余りに着目して、扱いやすい数字にどんどん置き換えていくことで、倍数であることを示したり余りを求めることが楽になりますね。
おわりに
ここでは、合同式を用いて、倍数であることを示したり、余りを求めたりする問題を見ました。複雑な状況でも、別の分かりやすい数字に置き換えていけるので、だいぶスッキリ解ける問題も出てきます。このページでも、1問目はそれほどありがたみがわからないかもしれませんが、2問目や3問目では、かなり使えることがわかると思います。