この問題解き方と、答え教えてください( ；꒳​； )

この問題解き方と、答え教えてください( ；꒳​； )

No.4 回答者： kairou 回答日時： 2020/11/30 21:52

4¹＝4 で余りは 4 。

4²＝16 で余りは 7 。
4³＝64 で余りは 1 。
4⁴＝256 で余りは 4 。
4⁵＝1024 で余りは 7 。
4⁶＝4096 で余りは 1 。
つまり 1, 4, 7 の繰り返し。
50÷3=16 余り 2 ですから
4⁵⁰ を 9 で割った余りは 7 。

No.3 回答者： ありものがたり 回答日時： 2020/11/30 21:46

冪乗の剰余に関するオイラーの定理

って知ってるべか。
a と m が互いに素であるとき、
a^φ(m) ≡ 1 (mod m) である。
ここで φ はオイラー関数って奴で、
φ(m) は 0 から m-1 までの整数のうち
m と互いに素数なものの個数。
m が素数 p の冪 m = p^k (kは自然数)
であるとき、φ(p^k) = (p^k)(1 - 1/p) である。
これ使って、a = 4, m = 3^2 のとき、
φ(3^2) = (3^2)(1 - 1/3) = 6,
4^6 ≡ 1 (mod 9).

以上を使うと、
4^50 = 4^(6・8+2) ≡ ((4^6)^8)(4^2) ≡ (1^8)(4^2) = 16 ≡ 7 (mod 9).

No.2 回答者： ShowMeHow 回答日時： 2020/11/30 21:28

4^nを９で割ったときの余りをｍとすると

4^n=9x+m
4^(n+1)
=4(9x+m)
になるから、4ｍを９で割ったときのあまりになる。
4²＝16で９で割ったときの余りは7
4³＝64で９で割ったときの余りは1だけど、これは7ｘ4＝28を9で割ったときの余りと同じ

よって、
2乗からから始めると、
7、1、4、7　と循環することになる。
50/3＝16余り2だから、（上の循環は二乗から始まっているので）7かな

No.1 回答者： varietyknowledge 回答日時： 2020/11/30 21:24

この問題は余りの周期性を利用する。

4^1÷9=4÷9=0 余り 4
4^2÷9=16÷9=1 余り 7
4^3÷9=64÷9=7 余り 1
4^4÷9=256÷9=28 余り 4

上記より3乗で1周期で4乗目は1乗と同じ余りになる。
よって、

4^50=4^(48+2)=4^(3×16+2)

より4^50を9で割った余りは7となる。

この回答へのお礼

ありがとうございます！！

お礼日時：2020/11/30 21:25