9の99999999乗の下9桁

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

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

解答を表示

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

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

x = 9^{99999999}

とおくと，

9 x = 9^{(10^{8})} = 3^{(2 \cdot 10^{8})} .

また，

φ

をオイラーのトーシェント関数とすると，

φ (2^{9}) = 2^{8} (2 - 1) = 2^{8}

であり，

3

と

2^{9}

は互いに素より，オイラーの定理から，

3^{(2 \cdot 10^{8})} = {3^{(2 \cdot 5^{8})}}^{2^{8}} = {3^{(2 \cdot 5^{8})}}^{φ (2^{9})} \equiv 1 \mod 2^{9} .

さらに，

φ (5^{9}) = 5^{8} (5 - 1) = 4 \cdot 5^{8}

であり，

3

と

5^{9}

は互いに素より，再びオイラーの定理から，

3^{(2 \cdot 10^{8})} = {3^{(2^{7})}}^{4 \cdot 5^{8}} = {3^{(2^{7})}}^{φ (5^{9})} \equiv 1 \mod 5^{9} .

2

と

5

は互いに素であるから，

9 x = 3^{(2 \cdot 10^{8})} \equiv 1 \mod 10^{9} .

したがって，

Z / 10^{9} 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 \mod 10^{9} .

∴

下

9

桁は

888888889.

投稿日：2023年11月24日

更新日：2023年12月8日

この記事を高評価した人

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

6126

コメントはありません。

読み込み中