数学ナビゲーター掲示板
HOME
HELP
新規作成
新着記事
ツリー表示
スレッド表示
トピック表示
発言ランク
ファイル一覧
検索
過去ログ
[ スレッド内全4レス(親記事-4 表示) ] <<
0
>>
■50146
/ 親記事)
合同式の計算
▼
■
□投稿者/ 画宇巣
一般人(11回)-(2019/11/04(Mon) 21:46:30)
合同式の計算の復習をしているところです。
下の画像の問題を以下のようにして解きましたが、問題ないのでしょうか?
2000 = 166・12 + 8
2000≡8 (mod 12)
2000^2000≡8^2000 = 8^(166・12+8) (mod 12)
8^(166・12+8)≡8^8 = 4096 (mod 12)
4096 = 341*12 + 4≡4 (mod 12)
∴2000^2000≡4 (mod 12)
780×1125 => 173×250
1572871590.jpg
/
112KB
引用返信
/
返信
[メール受信/OFF]
削除キー/
編集
削除
■50147
/ ResNo.1)
Re[1]: 合同式の計算
▲
▼
■
□投稿者/ らすかる
付き人(53回)-(2019/11/04(Mon) 22:07:33)
問題大ありです。
○^△(mod□)の剰余計算で
○にはmod□が使えますが、
一般に△にはmod□は使えません。
たまたま答えが合っただけです。
実際、
2000^2000を7で割ったときの余りは?
という問題で
2000=285×7+5から
2000^2000≡5^5=3125=446×7+3≡3(mod7)
と考えると正しくありません。
正解は2000^2000≡4(mod7)です。
引用返信
/
返信
[メール受信/OFF]
削除キー/
編集
削除
■50148
/ ResNo.2)
Re[2]: 合同式の計算
▲
▼
■
□投稿者/ 画宇巣
一般人(12回)-(2019/11/04(Mon) 22:52:15)
2019/11/04(Mon) 22:58:27 編集(投稿者)
すばやい回答ありがとうございます。合同式の計算も久しぶりですので混乱しております。
やはり指数には使えないのですね。いや、あまりに簡単すぎて怪しいとうすうす感づいていました(笑)。やはり画像のように地道に計算するしかないんですね。手計算だと相当メンドイ。
2000^2000
= (285×7+5)^2000
≡5^2000 = (5^5)^400 = 3125^400 = (446×7+3)^400 (mod7)
≡3^400 = (3^8)^50 = 6561^50 = (937×7+2)^50 (mod7)
≡2^50 = (2^10)^5 = 1024^5 = (146×7+2)^5 (mod7)
≡2^5 = 32 = 7×4+4 (mod7)
≡4 (mod7)
えーと、本来なら新規スレにすべきですが、指数絡みの話題ですので以下の件についてもお願いします。
10 = 2・4+2
6 = 1・4+2
10≡6 (mod 4)
であるとき
2^10 = 1024 = 4・256
2^6 = 64 = 4・16
∴2^10≡2^6 (mod 4)
3^10 = 59049 = 4・14762 + 1
3^6 = 729 = 4・182 + 1
∴3^10≡3^6 (mod 4)
これから推定すると整数 a、b、p、n について
a≡b (mod p) ⇒ n^a≡n^b
が成り立ちそうですけど、成り立ちますか?
引用返信
/
返信
[メール受信/OFF]
削除キー/
編集
削除
■50149
/ ResNo.3)
Re[3]: 合同式の計算
▲
▼
■
□投稿者/ らすかる
付き人(54回)-(2019/11/04(Mon) 23:47:48)
> やはり画像のように地道に計算するしかないんですね
いいえ、そんなことはないです。
指数に「同じ法」の剰余が使えないだけで、別の法の剰余は使えます。
2000^2000≡5^2000(mod7)
5^1≡5(mod7)
5^2≡5×5≡4(mod7)
5^3≡4×5≡6(mod7)
5^4≡6×5≡2(mod7)
5^5≡2×5≡3(mod7)
5^6≡3×5≡1(mod7)
5^7≡1×5≡5(mod7)
ですから
a≡b(mod6)のとき5^a≡5^b(mod7)です。
従って
5^2000=5^(333×6+2)≡5^2≡4(mod7)と求められます。
元の問題も
2000^2000≡8^2000(mod12)
8^1=8(mod12)
8^2=8×8≡4(mod12)
8^3=4×8≡8(mod12)
なので
a≡b(mod2)のとき8^a≡8^b(mod12)となりますので、
8^2000=8^(999×2+2)≡8^2≡4(mod12)
※2行上のa,bは1以上でないと成り立たないので0にしてはいけない
のようにできます。
> 整数 a、b、p、n について
> a≡b (mod p) ⇒ n^a≡n^b
> が成り立ちそうですけど、成り立ちますか?
成り立ちません。
反例:
1≡5(mod4)ですが2^1≡2^5(mod4)は成り立ちません。
引用返信
/
返信
[メール受信/OFF]
削除キー/
編集
削除
■50150
/ ResNo.4)
Re[4]: 合同式の計算
▲
▼
■
□投稿者/ 画宇巣
一般人(13回)-(2019/11/05(Tue) 01:02:03)
> 指数に「同じ法」の剰余が使えないだけで、別の法の剰余は使えます。
なるほど、なるほど!
とても勉強になります。いつも丁寧な回答ありがとうございます。
引用返信
/
返信
[メール受信/OFF]
削除キー/
編集
削除
このスレッドをツリーで一括表示
スレッド内ページ移動 / <<
0
>>
このスレッドに書きこむ
入力内容にタグは利用できません。
数式の記述方法
TeX入力ができます。
\[
TeX形式数式
\]
あるいは,
$
TeX形式数式
$
で数式を記述します。
TeX形式数式には半角英数字のみです。詳しくは、
ここ
を見てください。
Titleは質問の内容がわかりやすいように書いてください。
他人を中傷する記事は管理者の判断で予告無く削除されます。
半角カナは使用しないでください。文字化けの原因になります。
名前、Title、コメントは必須記入項目です。記入漏れはエラーになります。
入力内容の一部は、次回投稿時の手間を省くためブラウザに記録されます。
削除キーを覚えておくと、自分の記事の編集・削除ができます。
URLは自動的にリンクされます。
引用返信するときは不要な引用部分を削除してください。
記事中に No*** のように書くとその記事にリンクされます(No は半角英字/*** は半角数字)。
使用例)
No123 → 記事No123の記事リンクになります(指定表示)。
No123,130,134 → 記事No123/130/134 の記事リンクになります(複数表示)。
No123-130 → 記事No123〜130 の記事リンクになります(連続表示)。
Name
/
E-Mail
/
└> 関連するレス記事をメールで受信しますか?
NO
YES
/ アドレス
非公開
公開
Title
/
URL
/
Comment/ 通常モード->
図表モード->
(適当に改行して下さい/半角10000文字以内)
File
/
アップ可能拡張子=> /
.gif
/
.jpg
/
.jpeg
/
.png
/.txt/.lzh/.zip/.mid/.svg
1) 太字の拡張子は画像として認識されます。
2) 画像は初期状態で縮小サイズ250×250ピクセル以下で表示されます。
3) 同名ファイルがある、またはファイル名が不適切な場合、
ファイル名が自動変更されます。
4) アップ可能ファイルサイズは1回
200KB
(1KB=1024Bytes)までです。
5) ファイルアップ時はプレビューは利用できません。
6) スレッド内の合計ファイルサイズ:[112/500KB]
残り:[388KB]
Icon
/
ぺそぎん(常)
ぺそぎん(喜)
ぺそぎん(礼)
ぺそぎん(跳)
ぺそぎん(焦)
ぺそぎん(励)
マサト
ミツコ
サトシ
サクラ
ダン
エリカ
ホイールロボ
くるりロボ
ぱんだ
ふとめネコ
ねずみ
こあら
疑問ねこ
ランダム
管理者用
(画像を選択/
サンプル一覧
)
削除キー
/
(半角8文字以内)
解決済み!
BOX/
解決したらチェックしてください!
プレビュー/
Mode/
通常管理
表示許可
Pass/
HOME
HELP
新規作成
新着記事
ツリー表示
スレッド表示
トピック表示
発言ランク
ファイル一覧
検索
過去ログ
-
Child Tree
-
Edit By
数学ナビゲーター