10の累乗を13で割った余り

質問

10^1を13で割ると余り10
10^2を13で割ると余り9
10^3を13で割ると余り12
10^4を13で割ると余り3
10^5を13で割ると余り4
10^6を13で割ると余り1
10^7を13で割ると余り10
10^8を13で割ると余り9

というように余りが6個とばしで巡回しているんですがこれを証明するにはどうしたらいいでしょうか?
合同式というものが関係しているようなんですが・・・

あとこれを利用して
10^(10^k)を13で割った余りを求めたいんですけど
どういう風にしたらいいでしょうか?

回答No.5

R_Earl · ベストアンサー

「13で割ると余りがaになる数」は13n + a、
「13で割ると余りがbになる数」は13m + bとおけます(nとmは整数)。

「13で割ると余りがaになる数」と「13で割ると余りがbになる数」の積を13で割った余りは、
「abを13で割った余り」に等しくなります。
この証明は比較的楽なので、チャレンジしてみて下さい。

これができると、6個とばしで循環することが証明できます。
「10^6を13で割ると余り1」というのを利用します。

例えば10^9を13で割った時の余りを考えます。
まず10^9を
10^9 = (10^6)(10^3)
と分解します。
ここで

「13で割ると余りがaになる数」と
「13で割ると余りがbになる数」の積を13で割った余りは、
「abを13で割った余り」に等しくなる

という性質を利用すれば、「10^9を13で割った余り」は
「10^3を割った余り」に等しいことが言えます。

6個とばしで巡回する性質は、
この話を数学的帰納法と併用することで証明可能なはずです。

お礼

ありがとうございました。
数学的帰納法で無事論証することが出来ました。

回答No.4

owata-www

合同式がおわかりなら
10^n＝10^(n-6)*10^6≡10^(n-6)*1≡10^(n-6)
ということでお察しの通り６個飛ばしになります

＞10^(10^k)を13で割った余りを求めたいんですけど
どういう風にしたらいいでしょうか?

結局のところ
10^nを13で割った余りは
n≡0（mod 6）…１
n≡1　…10
n≡2　…9
n≡3　…12
n≡4　…3
n≡5　…4
となります

つまり10^kを6で割った余りを考えればいいわけです

お礼

ありがとうございました。
流れの大筋をつかむことが出来ました

回答No.3

bgm38489

10^7－10^1＝9999990ですね？これは、13の倍数！

回答No.2

chiezo2005

6桁違いの差が13で割り切れる。
つまり
10＾7-10＝9999990
は13で割り切れるからです。

これがわかれば、問題の答えも簡単にでます。

回答No.1

Tacosan

それこそ 10^6 (= 1,000,000) を 13 で割ったら余りが 1 になるって言えば終わり, だよね?
これを応用すると, 10^(10^k) を 13 で割った余りは 10^k を 6 で割った余りがわかればわかる, と.