modの計算で余りを求めたいのですけども？

質問

パソコンを使わないで57192^12357÷350のあまりを求めるにはどうしたらいいでしょうか？
ちなみに答えは320なのですが計算のやり方がわかりません。

回答No.6

killer_7 · ベストアンサー

下のように，合同式で地道に指数部分を小さくしていくのが素直で確実でしょう．

以下合同式は350を法とする．
57192≡142より，
57192^12357≡142^12357=(142^2)^6178 * 142
ここで，142^2=20164≡214より，
57192^12357≡214^6178 * 142=(214^2)^3089 * 142
214^2=45796≡296より，
57192^12357≡296^3089 * 142

以下同様にして，57192^12357≡302を得ます．
運良く，早い段階でループになり，楽に求めることができました．

まとめる際に2乗に限る必要はなく，
142^12357=(142^3)^4119
などとしてもよいです．
142^3など，計算が面倒なかわりに，
まとめる回数は少なくてすみます．
そのへんは場合によってお好みで．

回答No.8

age_momo

#4さんに似たアプローチですが。
142^12357の350で割った時の余りを350=2*5^2*7から互いに素な2と25と7に分割して連立してみます。

142≡0　(mod　2)
142^12357≡0　(mod　2)

142≡17　(mod　25)
17^12357=(15+2)^12357
=15^12357+C[12357,1]*15^12356*2+・・・+C[12357,2]*15^2*2^12355+12357*15*2^12356+2^12357　より
17^12357≡2^12356*(12357*15+2)≡7*2^12356≡7*2^6*1024^1235
≡7*64*(-1)≡-23≡2　(mod　25)　(∵15^2≡0　mod25)

142≡2　(mod　7)
142^6≡2^6≡1　(mod　7)
142^12357=142^3*(142^6)^2059より
142^12357≡2^3≡1　(mod　7)

全てを満たす0以上、350未満の整数は

302

です。

回答No.7

zk43

ふたたび、すみません。（zk43より）

また考えたのですが、
142と7、142と25は互いに素なので、オイラーの定理から、
142^6≡1（mod 7）
142^20≡1（mod 25）
最初の式を10乗、後の式を3乗して、
142^60≡1（mod 7）
142^60≡1（mod 25）
よって、142^60≡1（mod 175）
（7で割っても、25で割っても余り1で、7と25は互いに素なので）

また、計算機で地道に計算していくと、
142^2≡-33（mod 175）
・・・
142^7≡23（mod 175）
・・・
142^10≡149（mod 175）
142^20≡151（mod 175）
142^50≡74（mod 175）
となるので、
142^117≡142^(60+50+7）≡1×74×23≡1702≡127（mod 175）
になりました。

これより、
142^12357≡127（mod 175）
142^12357≡0（mod 2）
となって、142^12357は175で割ると127余る偶数なので、
142^12357＝127＋175(2n+1)＝350n＋302の形の数です。
よって、350で割ると、余りは302です。

なんか気持ち悪いので意地で計算してしまいました・・・

回答No.5

Mr_Holland

lick6さんとzk43さんが導いた「142^12357」から引き継いで見ます。
　フェルマーの小定理から
　　142^174≡1 (mod 175)
　両辺を71乗して、
　　142^12354≡1 (mod 175)
　両辺に142^3を掛けて
　　142^12357≡142^3 (mod 175)
　この式の右辺であれば電卓でも計算可能になり、113 (mod 175)と求められますが、もう少し分解しますと、
　　（右辺）≡(175-33)^3 (mod 175)
　　　　　　≡{-33^3} (mod 175)
　　　　　　≡{175-62} (mod 175)
　　　　　　≡113 (mod 175)
　あとは、zk43さんの「142^12357≡0（mod 2）・・・(4)」を考慮すると、
　　142^12357≡288 (mod 350)
となり、求める余りは288になります。（アレ、答えと違うな～）

回答No.4

zk43

57192^12357≡r（mod 350）・・・(1)
となるr（0≦r＜350）を求めるんですね。
計算は面倒くさそうです・・・

まず、57192≡142（mod 350）なので、(1)は、
142^12357≡r（mod 350）
となります。

142と350は互いに素ではないので、オイラーの定理はそのまま
では使えません・・・

まず、142は2で割り切れるので、
142≡0（mod 2）・・・(2)
また、142＝2×71、350＝2×175で、142と175は互いに素なので、
オイラーの定理によって、
142^120≡1（mod 175）・・・(3)
（指数の120はオイラーの関数φ(175)＝120より）

(2)の両辺を12357乗して、
142^12357≡0（mod 2）・・・(4)
(3)の両辺を102乗して、
142^12240≡1（mod 175）
さらにこの両辺に142^117を掛けると、
142^12357≡142^117（mod 175）・・・(5)
この右辺をとりあえず、142^117≡s（mod 175）として、
142^12357≡s（mod 175）・・・(6)

結局、(4)と(6)から、142^12357は連立合同式、
x≡0（mod 2）
x≡s（mod 175）
を満たし、これを解いてx≡r（mod 350）が求まると思います。
（これは、いわゆる、かの有名な中国の剰余定理。）

ただ、(6)のsが何か、計算が面倒なのでやってません・・・
ここがネックか？

回答No.3

lick6

合同式の使い方の例として
7^3 を 5 で割った余りを求めるとします。
7^3 = 343 ですから余りは 3 ですよね。
これを合同式を使ってとくと
7^3 ≡ 2^3 = 8 ≡ 3 (mod 5)
となります。
何故余りをあとからｎ乗しても平気なのかというと
7^n = (5 + 2)^n
でこれを展開すると 2^n 以外は全部 5 の何乗かがつきますね。

ただこの問題の場合 57192 ÷ 350 = 163 … 142 となり 142^12357 というのも到底計算できませんね。
おそらくここでフェルマーの小定理を使うのかと思います。
リンクを載せておくのであとはご自分でトライしてみてください。

参考URL：

http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86

回答No.2

kobby

302のような、、、

回答No.1

misan007

例えば７００で割って余りをまた３５０で割ったときの余りを
考えるとかですかね。。。