合同式を利用して様々な問題を解いていきます。
(例題1)
2つの整数\(a,b\)を\(6\)で割った余りがそれぞれ\(5,2\)である。このとき次の数を\(6\)で割ったときの余りを求めよ。
(1)\(a^2-4ab\)
(2)\(a^{200}+b^{100}\)
\(a≡5\),\(b≡2\) (\(\mathrm{mod}\) \(6\))
です。
\(a\)を\(5\)、\(b\)を\(2\)として(代入して)計算します。
です。
\(a\)を\(5\)、\(b\)を\(2\)として(代入して)計算します。
(解答)
以下、(\(\mathrm{mod}\) \(6\)) とする。
条件より、\(a≡5\),\(b≡2\) である。
(1)
\(a^2-4ab\)
\(≡(5)^2-4・5・2\)
\(≡25-40\)
\(≡-15\)
\(≡-15+6×3\)
\(≡3\)
よって余りは\(3\)
(2)
\(a^{2}≡25≡1\) なので、\(a^{200}\)はすぐに求まります。
一方\(b\)の累乗を計算しても、\(≡1\)とはなりません。ですが、何回か計算してみると規則性があるのがわかるのでそれを利用します。
一方\(b\)の累乗を計算しても、\(≡1\)とはなりません。ですが、何回か計算してみると規則性があるのがわかるのでそれを利用します。
\(a^{2}≡25≡1\) より
\(a^{200}≡(a^2)^{100}\)\(≡1^{100}≡1\)
また、
\(b^{2}≡4\) より
\(b^{3}≡b^{2}×b\)\(≡4×2≡8≡2\)
\(b^{4}≡b^{3}×b≡2×2≡4\)
\(b^{5}≡4×2≡8≡2\)
\(b^{6}≡2×2≡4\)
・・・ なので、\(b^{偶数}≡4\)
したがって
\(b^{100}\)
\(≡b^{2×50}\)
\(≡4\)
以上より
\(a^{200}+b^{100}≡1+4≡5\)
よって余りは\(5\)
(例題2)
\(2000^{2000}\)を\(12\)で割った余りを求めよ。
\(2000≡8\) (\(\mathrm{mod}\) \(12\))
より、\(8^2≡4\),\(8^3≡8\),\(8^4≡4\)・・・と規則性を見つけても解けますが、今回は式変形で\(2000^{2000}\)の次数を下げていく方法で解いてみます。(計算量は多くなります。)
\(2^{10}=1024\) を覚えておくとスムーズに計算できます。
より、\(8^2≡4\),\(8^3≡8\),\(8^4≡4\)・・・と規則性を見つけても解けますが、今回は式変形で\(2000^{2000}\)の次数を下げていく方法で解いてみます。(計算量は多くなります。)
\(2^{10}=1024\) を覚えておくとスムーズに計算できます。
(解答)
以下、 (\(\mathrm{mod}\) \(12\))とする。
以下、 (\(\mathrm{mod}\) \(12\))とする。
\(2000^{2000}\)
\(≡(8)^{2000}\)
\(≡(8^4)^{500}\)
\(≡(2^{12})^{500}\)
\(≡(4096)^{500}\)
\(≡(8)^{2000}\)
\(≡(8^4)^{500}\)
\(≡(2^{12})^{500}\)
\(≡(4096)^{500}\)
\((4096)^{500}\)
\(≡(4)^{500}\)
\(≡(4^5)^{100}\)
\(≡(2^{10})^{100}\)
\(≡(1024)^{100}\)
\(≡(4)^{500}\)
\(≡(4^5)^{100}\)
\(≡(2^{10})^{100}\)
\(≡(1024)^{100}\)
\((1024)^{100}\)
\(≡(4)^{100}\)
\(≡(4)^{100}\)
\(≡(4^5)^{20}\)
\(≡(1024)^{20}\)
\(≡(1024)^{20}\)
\((1024)^{20}\)
\(≡4^{20}\)
\(≡(4^5)^{4}\)
\(≡(1024)^4\)
\(≡4^4\)
\(≡256\)
\(≡4\)
\(≡4^{20}\)
\(≡(4^5)^{4}\)
\(≡(1024)^4\)
\(≡4^4\)
\(≡256\)
\(≡4\)
よって余りは\(4\)
(例題3)
\(83^{1234}\)の一の位を求めよ。
\(83^{1234}\)の一の位を求めよ。
一の位の数は、\(10\)で割った余りなので、\(\mathrm{mod}\) \(10\) を考えます。
(解答)
以下\(\mathrm{mod}\) \(10\) とする。
以下\(\mathrm{mod}\) \(10\) とする。
\(83≡3\) であり
\(3^2≡9\), \(3^3≡27≡7\), \(3^4≡81≡1\) なので
\(3^2≡9\), \(3^3≡27≡7\), \(3^4≡81≡1\) なので
\(83^{1234}\)
\(≡3^{1234}\)
\(≡3^{4×308+2}\)
\(≡(3^4)^{308}×3^{2}\)
\(≡9\)
\(≡3^{1234}\)
\(≡3^{4×308+2}\)
\(≡(3^4)^{308}×3^{2}\)
\(≡9\)
よって一の位は\(9\)
(別解)
掛け算の答えの一の位は、掛ける数の一の位どうしの掛け算からしか計算されないため、\(83×83\) の一の位は\(3×3=9\)です。以下\(83^3,83^4\)を計算していくと、
\(83^1\)の一の位:3
\(83^2\)の一の位：3×3=9
\(83^3\)の一の位：9×3=27 の一の位=7
\(83^4\)の一の位: 7×3=21 の一の位=1
\(83^5\)の一の位: 1×3=3
\(83^6\)の一の位：3×3=9
と、3→9→7→1→ 3→9→7→1→ 3・・・・ とループします。
\(3^{4の倍数}\) の一の位が1 なので、\(83^{1232}\) の一の位は1です。
よって、\(83^{1234}\)の一の位は 9となります。
掛け算の答えの一の位は、掛ける数の一の位どうしの掛け算からしか計算されないため、\(83×83\) の一の位は\(3×3=9\)です。以下\(83^3,83^4\)を計算していくと、
\(83^1\)の一の位:3
\(83^2\)の一の位：3×3=9
\(83^3\)の一の位：9×3=27 の一の位=7
\(83^4\)の一の位: 7×3=21 の一の位=1
\(83^5\)の一の位: 1×3=3
\(83^6\)の一の位：3×3=9
と、3→9→7→1→ 3→9→7→1→ 3・・・・ とループします。
\(3^{4の倍数}\) の一の位が1 なので、\(83^{1232}\) の一の位は1です。
よって、\(83^{1234}\)の一の位は 9となります。
今までの例題は、二項定理(数Ⅱ)を利用しても解くことができます。
二項定理を用いても結局は余りについてのみ考えることになるので、やることはさほど変わりません。ただ合同式に比べると、式が長くなり若干面倒になります。
二項定理を用いても結局は余りについてのみ考えることになるので、やることはさほど変わりません。ただ合同式に比べると、式が長くなり若干面倒になります。
以上になります。お疲れさまでした。
ここまで見て頂きありがとうございました。