インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

499:素数カクテル

499

499は素数。素数カクテルの値段。

Cafe+Bar Ludzie

大阪大学豊中キャンパスの坂下に学生のみで運営されているLudzie(ルジェ*1)という素敵なカフェバーがあります。
資金面、技術面ともに一切外部サポートを受けずに一から作り上げたというから驚きです。

Ludieには何故か『素数カクテル』という世にも珍しい素敵な商品があります!
f:id:integers:20160127084425j:plain
f:id:integers:20160127084644j:plain

値段は勿論素数ということで、499円!

一体、どんな味がして、どこが素数なのか!?是非とも一度石橋まで足を運んでみてください!!

499^{499}の下六桁

突然ですが、計算をしたくなったので「499^{499}1000000で割った余り」の計算をしてみましょう。

tsujimotter氏の記事
tsujimotter.hatenablog.com

では「3^{100}19で割った余り」を計算しました。Fermatの小定理を使えば3^{18}\equiv 1 \pmod{19}が分かるので少ない計算で答えを求めることができました。

しかしながら、Fermatの小定理を一般化したEulerの定理を用いても499^{400000} \equiv 1 \pmod{10^6}となって今回の計算には役立ちません。そこで、「6桁×6桁の計算ぐらいだったら苦ではない」と仮定して素朴に計算してみようと思います。

499^2=249001

499^3=249001\times 499=124251499 \equiv 251499\pmod{10^6}

499^4 \equiv 249001^2 = 62001498001 \equiv 498001 \pmod{10^6}

499^8 \equiv 498001^2 = 248004996001 \equiv 996001 \pmod{10^6}

499^{16} \equiv 992001^2 = 992017992001 \equiv 992001 \pmod{10^6}

499^{32} \equiv 992001^2 = 984065984001 \equiv 984001 \pmod{10^6}

499^{64} \equiv 984001^2 = 968257968001 \equiv 968001 \pmod{10^6}

499^{128} \equiv 968001^2 = 937025936001 \equiv 936001 \pmod{10^6}

499^{256} \equiv 936001^2 = 876097872001 \equiv 872001 \pmod{10^6}

499^{384} = 499^{256+128} \equiv 872001\times 936001 = 816193808001 \equiv 808001 \pmod{10^6}

499^{448} = 499^{384+64} \equiv 808001\times 968001 = 782145776001 \equiv 776001 \pmod{10^6}

499^{480} = 499^{448+32} \equiv 776001\times 984001 = 763585760001 \equiv 760001 \pmod{10^6}

499^{496} = 499^{480+16} \equiv 760001\times 992001 = 753921752001 \equiv 752001 \pmod{10^6}

499^{499} = 499^{496+3} \equiv 752001\times 257449 = 189127499499 \pmod{10^6}

というわけで、499^{499} \equiv 499499 \pmod{10^6}がわかりました。

5^5=3125 \equiv 5 \pmod{10}11^{11} = 285311670611 \equiv 11\pmod{100}のように、p^pの10進法表記の終わりの桁がpになる例はたくさん存在しますが、pが2回並んで終わる例は499^{499}しか知られていないようです。

*1:ポーランド語で「人びと」の意。