2^1201を1925で割った余りを求めるにはどのように解いたらいいですか？ 合同式の問題です。 カ

2^1201を1925で割った余りを求めるにはどのように解いたらいいですか？
合同式の問題です。



カテゴリが分かりません。

No.1 回答者： t_fumiaki 回答日時： 2022/07/29 17:05

2¹²⁰¹=(2¹¹)¹⁰⁹×2²=2048¹⁰⁹×4≡123¹⁰⁹×4=(123²)⁵⁴×123×4

≡7⁵⁴×492=(7⁴)¹³×492=2401¹³×492≡1×492=492

余り：492

No.2 回答者： windwald 回答日時： 2022/07/29 20:13

こういうのは変に正解だけを見ると分からなくなります。

正解だけを見ると、どうしてそういう式変形をしたのかが分からず、できる人だけの特別なものの見方があるんじゃ無いか、みたいに思えてしまうだけです。

「いろいろやってみる」ことで「どうやったら答えが出せそうか」が分かるようになります。これが近道です。

合同式を使って余りを求める方法というものがどういうものか、まず分かっていらっしゃいますでしょうか。

たとえば、100を7で割った余りを求めてみます。
　100÷7＝14あまり2
ですけれども、これを考えるときに、
……、7*13＝91、7*14=98、7*15=105
のように考えて、100を超えない7の倍数の最大値が7*14=98だとわかり、そのうえで100-98=2によりあまり2を出していますね。
これを合同式で書くと　100≡2(mod 7) となります。

次に合同式の性質を利用することを考えます。文字式は全て自然数として
a≡b(mod n) のとき、nと互いに素なmに対して、ma≡mb(mod n)が言えます。
例えば、100*10=1000を7で割ると1000=7*142+6よりあまり6ですが、合同式を使えば、
1000=10*100≡10*2=20 (mod 7) ですので
さらに20=14+6より 20≡6 (mod 7) であまり6と分かります。

また、a≡b (mod n)のとき、a^m≡b^m (mod n)です。
たとえば 10≡3 (mod 7) ですから
10^2≡3^2=9≡2 (mod 7) となりますし、10^3≡3^3＝27≡6(mod 7)です。

次に 2^12 を 7 で割ったあまりを考えてみましょうか。
このくらいならば2^12=4096ですから、4096＝7*585+1より、あまり1と求めることができます。しかしもうちょっと楽にならないものでしょうか。
そこで合同式の性質を使うのです。2^12を(2^2)^6 と捉えてみましょう。
2^2＝4ですから、2^2≡4(mod 7)です。
よって(2^2)^6≡4^6 (mod 7)となります。
あまり計算が楽になりませんでした。
ではカッコの中身をもう少し大きくしてみましょう。2^12＝(2^3)^4とします。
2^3＝8ですから、2^3≡1 (mod 7) です。
よって (2^3)^4≡1^4=1 (mod 7) と非常に簡単になりました。

蛇足ですが、2^12＝(2^4)^3 とすると、2^4=16より2^4≡2(mod 7)
よって(2^4)^3≡2^3=8≡1(mod 7)。
かえって面倒になった感があります。

このように、指数の中身を割る数である7よりもちょっぴりだけ大きくしておくと、合同式の計算が楽になると言うことが分かりますね。

そこでようやく本題です。
2^1201を1925で割った余りを求めます。今やったように、累乗と合同式の性質を利用すると非常に楽になります。そこで2の累乗のうち1925を超える初めての数を見つけます。
……、2^10＝1024、2^11＝2048 ですからこいつです。
そこで2^1201=2^2*(2^11)^109＝4*2048^109とします。
2048を1925で割るとあまりは123と簡単に求まりますから、
4*2048^109≡4*123^109 (mod 1925) となります。
あとは123を109回掛けるだけ……、いやまだやりたくないですね。
123^2＝15129を使いましょう。
4*123^109＝4*123*(123^2)^54＝492*15129^54 で、15129を1925で割ったあまりは少々面倒ですけど求められますね。1654です。
よって492*15129^54≡492*1654^54 (mod 1925) となります。
1654^54もできれば力技の計算はやりたくないですよね。ですからもう一度累乗と合同式の性質をさらに使っていきます。
1654^2もあまりやりたくないのでこれを使います。
1654≡-271 (mod 1925)、(-271)^2＝73441≡291 (mod 1925)より
492*1654^54≡492*(-271)^54≡492*291^27 (mod 1925)
さらに291^2＝84681≡1906≡-19 (mod 1925)ですから
492*291^27＝492*291*(291^2)^13≡492*291*(-19)^13
以下略です。

ところでまだまだ少々面倒くさいですね。もっと楽にできないものでしょうか。
実は2^15=32768と1925*17=32725が比較的近いことを見つけると、
2^1201＝2*(2^15)^80より
2*32768^80≡2*43^40 (mod 1925)
さらに43^2＝1849≡-76 (mod 1925)
2*(43^2)^20≡2*(-76)^20 (mod 1925)
以下略となります。

なお、#1さんの答えは途中計算に誤りがありますので最終的な答えは間違っています。

ところでカテゴリは数学以外の何が良いと思いますか？

No.3 回答者： ありものがたり 回答日時： 2022/07/29 21:52

1925 = 5²・7・11 ですから、オイラー関数の値は

φ(1925) = φ(5²)φ(7)φ(11)
　　　　= (5² - 5)(7 - 1)(11 - 1)
　　　　= 20・6・10
　　　　= 1200.
オイラーの定理より 2^φ(1925) ≡ 1 (mod 1925)
なので、
2^1201 = (2^1200)(2^1) ≡ 1・2 = 2 (mod 1925)
です。

No.4 回答者： t_fumiaki 回答日時： 2022/07/30 11:55

計算まちがった。

普通にやる。

2¹²⁰¹=(2³⁰)⁴⁰×2¹≡(1849)⁴⁰×2¹=(1849²)²⁰×2≡1²⁰×2=2
答：2