【応用】合同式を使って余りを求める

ここでは、合同式を使って、いろいろな余りを求める問題を見ていきます。

合同式を使って余りを求めるその１

【応用】合同式で見たように、合同式を使えば余りを簡単に調べることができます。このとき、使える内容をもう一度まとめておきましょう。

これより、和・差・積・べき乗を、合同なわかりやすい数に置き換えて考えることができます。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つで解いています。合同式を使う方法は、この場合分けの方法に対応していますが、この問題の場合は、まだ合同式を使うメリットはまだそんなに大きくありません。

合同式を使って余りを求めるその２

【応用】合同式の最後で見た内容とほぼ同じです。 $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$ が見つかったからよかったものの、見つからなかったら大変です。実は、こういう数が見つかるための条件は知られているのですが、それはまた別の機会で見ることにします。

合同式を使って余りを求めるその３

例えば、 $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問目では、かなり使えることがわかると思います。