0

9の99999999乗の下9桁

39
0
$$$$

$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.$

投稿日:20231124
更新日:2023128
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。

投稿者

Mathお
Mathお
43
5578

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中