A 回答 (4件)
- 最新から表示
- 回答順に表示
No.3
- 回答日時:
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.2
- 回答日時:
こういうのは変に正解だけを見ると分からなくなります。
正解だけを見ると、どうしてそういう式変形をしたのかが分からず、できる人だけの特別なものの見方があるんじゃ無いか、みたいに思えてしまうだけです。「いろいろやってみる」ことで「どうやったら答えが出せそうか」が分かるようになります。これが近道です。
合同式を使って余りを求める方法というものがどういうものか、まず分かっていらっしゃいますでしょうか。
たとえば、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.1
- 回答日時:
2¹²⁰¹=(2¹¹)¹⁰⁹×2²=2048¹⁰⁹×4≡123¹⁰⁹×4=(123²)⁵⁴×123×4
≡7⁵⁴×492=(7⁴)¹³×492=2401¹³×492≡1×492=492
余り:492
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 合同式について 3 2022/05/03 23:14
- 数学 x^nを(x-1)^2で割ったときの余りを求めよ 2 2022/04/23 16:08
- 物理学 カッコ1でこの状態での張力Tを求める問題でその時にはTの力が分解されていました。カッコ2ではbの糸を 12 2023/07/13 23:41
- 高校 三角形の辺の長さを求める問題で余弦定理で二次方程式を解いた時に答えが2つでてしまってどちらも正なので 3 2022/09/08 17:42
- その他(教育・科学・学問) 小学生の算数の商について 3 2023/03/06 14:11
- 数学 nC2=2016 の等式を満たす正の整数nの値を求める問題で n(n-1)/2=2016 n^2-n 4 2023/04/07 16:58
- 大学受験 合同式 1 2022/09/03 12:37
- 大学受験 助けてください。 大学入試まであと38日なのですが英語が2割です…。 第1志望は5割位なのですが、2 8 2023/01/03 19:37
- 数学 2次方程式 x^2=4x の解の求め方の誤答のどこが間違っているのかという問題があり、その模範解答が 6 2022/08/25 22:11
- 数学 写真(URL)の問題の(1)についてですが、 円c1は 2点を通ると書いてあることから、 2点の座標 5 2023/02/14 19:44
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
確率
-
2は5で割り切れません。 あまり...
-
負の余りはあり得ますか?
-
4の100乗を、7で割った余りとい...
-
7^100を6で割った余りを求めよ...
-
小学校4年生の算数の教科書で...
-
1 から 9 までの数字を使って引...
-
数字のトリック??
-
これの求め方を教えて下さい!...
-
5進法の計算問題の解き方
-
10進法⇒2進法には何故2で割るか
-
整式 P(x)を(x-1)²で割ったとき...
-
場合の数
-
13500を何時間何分に直すと? 1...
-
下記の問題について、「5は素数...
-
190分はなん時間何分ですか?
-
解き方を教えてください。 中3...
-
証明
-
数学 連続した3つの奇数の和は...
-
整式F(x)を x-1 で割ると5余り...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
小学校4年生の算数の教科書で...
-
190分はなん時間何分ですか?
-
ある整数を7ではると、商が10で...
-
数学の質問です。 下記の問いの...
-
2は5で割り切れません。 あまり...
-
解き方を教えてください。 中3...
-
負の余りはあり得ますか?
-
0から9までの数字を使ってでき...
-
下記数学Aの答えは36個ですが、...
-
高1数学Aの問題で、 「a、bは整...
-
10進法⇒2進法には何故2で割るか
-
これの求め方を教えて下さい!...
-
nが3の倍数でないとき
-
順列、組み合わせの問題です。 ...
-
4の100乗を、7で割った余りとい...
-
小学生への割り算の答えの確か...
-
1 から 9 までの数字を使って引...
-
〖エクセル〗MOD関数で、小さな...
-
1から9の数字を書いたカードが...
-
整式F(x)を x-1 で割ると5余り...
おすすめ情報