プロが教える店舗&オフィスのセキュリティ対策術

2019^2019を31で割ったときのあまりを求めよ。

解答は8ですが、1になってしまいます。
どこが間違えてるか教えてください

2019^3≡1(MOD31)
だから
(2019^3)^673≡1^673
よって、
余りは1

A 回答 (6件)

2019^3≡1(MOD31)ではなく


2019^3≡2(MOD31)だよ。
以下(MOD31)は省略
これから
2019^9=(2019^3)^3≡2^3=8
一方フェルマの定理から
2019^30≡1 これから、2019^2010=(2019^30)^67≡1
ゆえに
2019^2019=(2019^2010)(2019^9)≡1・8=8(MOD31)
    • good
    • 0

2019³


=8230172859
=8230172857 + 2
=265489447×31 + 2
    • good
    • 0

法が 31 なので φ(2019) は無関係ではないかと>#3. 底を mod 31 で, 指数を mod φ(31) でそれぞれ減らせばちょっとは楽.



341 が底2 に対する (フェルマー) 擬素数ってのも地味に背景にあるかもしれん.
    • good
    • 0

2019 = 31×65 + 4 より


mod 31 で
2019 ≡ 4.
よって
2019^2 ≡ 4^2 = 16,
2019^3 ≡ 16×4 = 64 ≡ 2,
2019^4 ≡ 2×4 = 8,
2019^5 ≡ 8×4 = 32 ≡ 1. ←[*]
ここまでやってみると、
2019^k の k を mod 5 で考えればよいことが判る。
2019 = 5×403 + 4 より
2019^2019 = 2019^(5×403 + 4) = ((2019^5)^403)(2019^4)
≡ (1^403)(4^4) = 256 = 31×8 + 8 ≡ 8.

今回の場合、φ(2019) = φ(3) φ(673) = (3-1)(673-1) = 1344
が大きすぎてオイラーの定理は使いにくい。
地道に [*] を発見するのが吉と見た。
    • good
    • 0

2019^1/31 ⇒ 余り4


2019^2/31 ⇒ 余り16
2019^3/31 ⇒ 余り2
2019^4/31 ⇒ 余り8
2019^5/31 ⇒ 余り1
2019^6/31 ⇒ 余り4

より、周期5で余りが循環する。
よって、2019^2019=2019^(2015+4)より余りは8
    • good
    • 1

2019^3≡1(MOD31)


のところ.
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!