数A (2)の解説をお願いします なんでこうなるのかがわかりません a^3をmで割った余り＝r^kを

数A
(2)の解説をお願いします
なんでこうなるのかがわかりません
a^3をmで割った余り＝r^kをmで割った余り
ということが成り立つのがわかります
でもこの問題はどうやってこれに当てはめて考えればいいのか、答えを見てもわかりませんでした。
教えてください！

No.2 ベストアンサー 回答者： hakasetarochan 回答日時： 2018/03/04 15:06

これでわかりますか？

No.4 回答者： varietyknowledge 回答日時： 2018/03/04 16:03

まず累乗は以下の性質を持ちます。

x^2=x*x
：2個のxの掛け算

x^3=x*x*x
：3個のxの掛け算

x^n=x*x*x*…
：n個のxの掛け算

x^(a+b)=(x^a)*(x^b)=(x^b)*(x^a)
x^(a*b)=(x^a)^b=(x^b)^a

で、今回の問題ですが、

3^100=3^(1+99)=3^1*3^(99)=3*3^(3*33)=3*(3^3)^33=3*(27)^33

に変形できます。

3/13は商が0、余りが3になります。
27/13は商が2、余りが1になります。
また、上記の性質から、27^33は33個の27の掛け算になります。

33個の27を個々で13で割った余りを考えると、27/13の余りは常に1になります。
同様に3/13の余りは3になります。
よって、余りの計算は、

3*(1)^33

になります。
1は何乗しても結果は1なので、求める答えは、

3*(1)^33=3*1=3

になります。

No.3 回答者： metabolian 回答日時： 2018/03/04 15:41

No.1さんの提示してくれた写真で、

「和、差、積の余り」の3.のところを見ると、
「abをmで割った余りは、rr'（a,bをそれぞれmで割った余り同士の積）をmで割った余りに等しい。」
ここでb=aとおけば、「a^2をmで割った余りは、r^2をmで割った余りに等しい。」
ここから3.を何度も使用して、
「a^kをmで割った余りは、r^kをmで割った余りに等しい。（k：整数）」…（Ａ）
が導けます。

(A)と指数法則（p^ab=(p^a)*(p^b) など）を利用すれば、3^100の計算をわざわざ計算しなくても、
余りが求められる…というわけです。

解答では、3^3=27（⇒たまたま余りが1なので、あとの計算がしやすい）を利用してますが、
3^4=81（⇒13で割った余りは3（81=13*6+3））…（B）を利用すると
※ちょっと長いですが

3^100=3^(4*25)=(3^4)^25
ここで(A)と(B)より、
(3^4)^25を13で割った余り
=(3)^25を13で割った余り ※3^4の部分を（13で割った余り）3に置き換えている。

同様にして、3^25=3^(4*6+1)=((3^4)^6)*3を13で割った余りは
((3)^6)*3=3^7を13で割った余りと等しく、
さらに、3^7=(3^4)*(3^3)を13で割った余りは
(3)*(3^3)=3^4を13で割った余りと等しく、結局3になります。

質問を見る限り、（A）の部分をちょっとだけ勘違いされてるように感じます…。

No.1 回答者： hakasetarochan 回答日時： 2018/03/04 14:56

まず、