08-01大きい累乗の余りを求める(難易度2)

合同式を利用し、$2019^{2019}$を$5$で割ったときの余りを求めよ。

合同式の性質である$a^n \equiv b^n(\bmod)$を利用しよう

$2019\equiv4(\bmod5)$
$4^2\equiv16\equiv1(\bmod5)$

$2019^{2019}\equiv4^{2019}\equiv4\cdot(4^2)^{1009}\equiv4(\bmod5)$


累乗の余りを求めるときは、底と指数を小さくして計算します。
$a\equiv b(\bmod5)$のとき$a^n\equiv b^n(\bmod5)$となることを利用し
 $2019\equiv4(\bmod5)$のとき、$2019^{2019}\equiv4^{2019}(\bmod5)$
$1^n=1$ということを利用するため、$4$の累乗の余りをさがし、$4^2\equiv1(\bmod5)$を見つけます。
 $4^{2019}\equiv4\cdot(4^2)^{1009}\equiv4\cdot(1)^{1009}\equiv4(\bmod5)$
と変形させて、解となります。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする