9の99999999乗の下9桁

$9^{99999999}$の下$9$桁を求めよ.

$9$つの$9$に関する$9$がゲシュタルト崩壊しそうな自作問題です．

解答を表示

以下の初等整数論におけるオイラーの定理を用いて解きます．

オイラーの定理
$\varphi$をオイラーのトーシェント関数($\varphi(n)$は$n$と互いに素な$n$以下の自然数の個数)とする．
自然数$n$に対して，$a$を$n$と互いに素な自然数としたとき，
$$ a^{\varphi(n)} \equiv 1 ~~\mathrm{mod}~n ,$$
となる．

$x=9^{99999999}$とおくと，
$9x=9^{(10^8)}=3^{(2 \cdot 10^8)}.$
また，$\varphi$をオイラーのトーシェント関数とすると，
$\varphi(2^9)=2^8 (2-1)=2^8$であり，$3$と$2^9$は互いに素より，オイラーの定理から，
$3^{(2 \cdot 10^8)}=\left\{ 3^{(2 \cdot 5^8)} \right\}^{ 2^8}=\left\{ 3^{(2 \cdot 5^8)} \right\}^{\varphi(2^9)} \equiv 1 ~~\mathrm{mod}~ 2^9.$
さらに，$\varphi(5^9)=5^8 (5-1)=4 \cdot 5^8$であり，$3$と$5^9$は互いに素より，再びオイラーの定理から，
$3^{(2 \cdot 10^8)}=\left\{ 3^{(2^7)} \right\}^{4 \cdot 5^8}=\left\{ 3^{(2^7)} \right\}^{\varphi(5^9)} \equiv 1 ~~\mathrm{mod}~ 5^9.$
$2$と$5$は互いに素であるから，
$9 x=3^{(2 \cdot 10^8)} \equiv 1 ~~\mathrm{mod}~ 10^9.$
したがって，$\mathbb{Z} / 10^9 \mathbb{Z}$における$9$の乗法的逆元$9^{-1}$を求めればよい.
$10^9-9 \cdot 111111111=1 $より，
$9^{-1}=-111111111$
よって，$9 x \equiv 1 \Leftrightarrow x \equiv 9^{-1}=-111111111 \equiv 888888889 ~~\mathrm{mod}~ 10^9.$
$\therefore$下$9$桁は$888888889.$

投稿日：2023年11月24日

更新日：2023年12月8日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

Mathお

4655

他の人のコメント

コメントはありません。

読み込み中

Mathお

9の99999999乗の下9桁