■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)は成り立ちません。
|
|