大きな数のべき乗をある数で割った余りを求める問題では、通常の累乗計算をそのまま行うことは困難です。そのような場合は、合同式の性質やオイラーの定理、素因数分解などを利用して計算を簡略化します。
この記事では、114514^1919を810で割った余りを求める方法について、途中の考え方を丁寧に解説します。単なる答えだけではなく、同じような問題にも応用できる計算手順を紹介します。
まず810を素因数分解して考える
合同式の計算では、割る数を扱いやすい形に分解すると解きやすくなります。810を素因数分解すると、
810=81×10=3^4×2×5
となります。つまり、810は2、3、5の因子を持つ数です。このような場合、各因子について余りを考えることで計算を簡単にできます。
特に、互いに素な数に分けて考え、最後に中国剰余定理を利用して戻す方法が有効です。
114514を810で割った余りを確認する
まず底となる114514を810で割った余りを求めます。
810×141=114210なので、
114514-114210=304
したがって、
114514≡304（mod 810）
となります。よって求める値は、
304^1919 mod 810
を計算すればよいことになります。
304の性質を利用してべき乗を簡単にする
304を810の素因数ごとに考えます。
まず3について見ると、304は3で割ると余り1になります。
304≡1（mod 3）
なので、何乗しても、
304^1919≡1（mod 3）
です。
次に2について考えると、304は偶数なので、
304^1919≡0（mod 2）
になります。
さらに5について見ると、304は5で割ると余り4なので、
304≡4≡-1（mod 5）
となります。
したがって、
304^1919≡(-1)^1919≡-1≡4（mod 5）
です。
中国剰余定理を使って810での余りを求める
ここまでで、求める数xについて以下の条件が分かりました。
x≡0（mod 2）
x≡1（mod 3）
x≡4（mod 5）
これらを満たす数を810未満で探します。
まず2と5の条件から、xは10で割った余りが4になる必要があります。
つまり、
x≡4（mod 10）
です。
10の倍数に4を足した形で考えると、x=10k+4となります。
これを3で割った余りが1になる条件に合わせます。
10k+4≡k+1（mod 3）
なので、
k+1≡1（mod 3）
より、
k≡0（mod 3）
となります。
したがって、k=3mと置くと、
x=30m+4
になります。
810未満でこの形の数を考えると、304が条件を満たします。
実際に確認すると、304は偶数で、3で割ると余り1、5で割ると余り4なので条件を満たします。
計算結果の確認
以上より、
304^1919≡304（mod 810）
となります。
したがって、
114514^1919 mod 810の答えは304です。
今回の計算では、べき乗を直接計算するのではなく、合同式によって底の性質を調べることで大幅に簡略化しました。
大きなべき乗の合同式問題を解くポイント
今回のような問題では、最初に割る数を素因数分解することが重要です。810のように複数の素数の積になっている場合、それぞれの合同条件に分けることで計算量を減らせます。
また、底の数が割る数と互いに素である場合には、オイラーの定理やフェルマーの小定理を使って指数を小さくすることもできます。
大学入試や整数問題では、大きな数字そのものを計算するのではなく、数字が持つ性質を利用することが解答への近道になります。
まとめ｜114514^1919 mod 810は合同式で簡単に求められる
114514^1919を810で割った余りは、114514を304に置き換え、810を素因数ごとに分解して考えることで求められます。
計算の流れは、底を簡単な形にする、割る数を分解する、それぞれの合同条件を求める、最後に条件を満たす数を決定するという手順です。
この方法は、非常に大きな指数を含む合同式の問題全般に応用できるため、整数問題を解く上で重要な考え方になります。
コメント