なんで7の100乗を6で割った余りが1なの？

こんにちは。相城です。今回はタイトルの通り, 何で $7^{100}$ を6で割った余りが1になるのかという, 素朴な疑問を解決しておこうと思います。結構解答などではさらっと書いているので, 理屈が分からない人にとっては, 何で？ってなることがあるかもしれません。それではどうぞ。

二項定理の最後の項だけ見ればいい

まず, $7=6\cdot1+1$ ですね。
そこで, $7^{100}$ の7を $6\cdot1+1=6+1$ に置き換えると,
$\left(6+1\right)^{100}$ となります。これを二項定理を用いて展開していくと,
${}_{100}\mathrm{C}_0 6^{100}+{}_{100}\mathrm{C}_1 6^{99}\cdot1^1+{}_{100}\mathrm{C}_2 6^{98}\cdot1^2+\cdots{}_{100}\mathrm{C}_{99} 6^1\cdot1^{99}+{}_{100}\mathrm{C}_{100} 1^{100}$
このとき, 最後の ${}_{100}\mathrm{C}_{100} 1^{100}=1^{100}=1$ 以外の項には6が少なくとも1個は入っているので, 6で割り切れます。したがって, 最後のこの項の数である1を6で割った余りが求める余りとなります。したがって, 余りは1になります。このように, 最後の部分を割っていけば余りは求まる仕組みになっています。合同式はこの余りだけに着目するようにできてるんだなと感じております。
次は合同式を使って解いてみましょう。

合同式を用いると

合同式を用いると秒殺です。
7は6で割ると余りが1なので, 6を法とすると,
$7\equiv1\ (\text{mod}\ 6)$
合同式は累乗できるので辺々100乗すると,
$7^{100}\equiv1^{100}\ (\text{mod\ }6)$
よって,
$7^{100}\equiv1\ (\text{mod}\ 6)$
したがって, 求める余りは1

二項定理の最後の項だけ見ればいい

合同式を用いると

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル