数学ナビゲーター掲示板

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

■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 >>

このスレッドに書きこむ

Mode/  Pass/

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

- Child Tree -
Edit By 数学ナビゲーター