Matematické Fórum

stuart clark · 28. 05. 2012 06:19

Last $3$ Digits of $9^{9^{9^{9}}}$

jardofpr

stuart clark

↑ jardofpr:

Thanks

To jardofpr: can we solve it Using Congruency Method.

Thanks

jardofpr · 01. 06. 2012 16:37

↑ stuart clark:

actually, I don't think I can do it that way now,
because, in fact, I've never used that method and I have to study it a bit before I'll try

so, if we can solve it that way,
I'm sure somebody else can do it spending much less time :)

check_drummer · 01. 06. 2012 22:25

↑ stuart clark:
Hi, schematically:
$9^9\equiv 9 \mod 160$
$9^{9^9}\equiv 9^9\equiv 89 \mod 400$
$9^{9^{9^9}} \equiv 9^{89}\equiv 289 \mod 1000$
So the last 3 digits are 289.
Modulus are values of the $\varphi$ function of the next modulus (e.g. $\varphi(1000)=400$ ).

vanok · 03. 06. 2012 20:12 — Editoval vanok (06. 06. 2012 14:17)

Hi ↑ stuart clark:,
Here is an using proof only: Euler's theoremOdkaz and chinese remainder theorem

Let us put
$A_1=9$
$A_2= 9^9$
$A_3= 9^{9^9}$
$A_ 4=9^{9^{9^9}}$
As $1000=8\cdot125$ , to calculate $A_4 \mod 1000$ it suffices to find, $A_4 \mod 8$ and $\mod125$
We have at once $A_4 \equiv 1 \mod 8$ ,
for the calculation of $A_4 \mod 125$ , it suffices to find $A_3 \mod 100$ , because $\varphi(125)= 100$ .
But $100=4\cdot 25$ , and it is enough to find $A_3 \mod 4$ and $\mod 25$ .
We have at once $A_3 \equiv1 \mod 4$ and for the calculation of $A_3 \mod 25$ , it suffices to find $A_2 \mod 20$ , because $\varphi ( 25 )= 20$
But $20=4\cdot 5$ and it suffices to find $A_2 \mod 4$ and $\mod 5$ .
We have at once $A_2=1 \mod 4$ and for the calculation of $A_2 \mod 5$ , it suffices to find $A_1 \mod 4$ because $\varphi( 5 ) =4$ .

Let us complete the calculations:
$A_1\equiv 1 \mod 4$
$A_2 \equiv 1 \mod 4$ and $A_2 \equiv 9^1 \equiv 4 \mod 5$ , thus $A_2 \equiv 9 \mod 20$
$A_3 \equiv 1 \mod 4$ and $A_3 \equiv 9^9 \equiv 9 \cdot ( 9^2) ^4 \equiv 9 \cdot (6^4 ) \equiv 9 \cdot ( 6^2 ) ^2 \equiv 9\cdot (-11)^2 \equiv 9\cdot (-4)\equiv -36\equiv 14 \mod 25$ , thus $A_3 \equiv 89 \mod 100$
Finally
$A_4 \equiv1 \mod 8$ and $A_4 \equiv 9^{89} \equiv 9\cdot (9^2)^ {44}\equiv 9\cdot ((9^2 )^ 2 ) ^{22}\equiv 9\cdot ((9^2 )^ 2 )^2 )^{ 11} \equiv39 \mod 125$ , thus $A_4 \equiv 289 \mod 1000$

Autor skryl část textu. Zobrazit/skrýt!

check_drummer · 03. 06. 2012 22:32

↑ vanok:
Hi,
from $9^{160}\equiv 1 \mod 400$ and form $9^9 \equiv 9 \mod 160$ it follows that $9^{9^9} \equiv 9^9 \equiv 89 \mod 400$ .
So where is mistake in my reasoning, please?

stuart clark · 05. 06. 2012 06:28

Thanks ↑ vanok: & ↑ check_drummer:

vanok · 06. 06. 2012 11:52

↑ check_drummer:
You have good answer, I was confusedwith mod 1000

Matematické Fórum

#1 28. 05. 2012 06:19

Last 3 digit

#2 30. 05. 2012 01:26 — Editoval jardofpr (30. 05. 2012 01:27)

Re: Last 3 digit

#3 31. 05. 2012 17:20 — Editoval stuart clark (31. 05. 2012 17:21)

Re: Last 3 digit

#4 01. 06. 2012 16:37

Re: Last 3 digit

#5 01. 06. 2012 22:25

Re: Last 3 digit

#6 03. 06. 2012 20:12 — Editoval vanok (06. 06. 2012 14:17)

Re: Last 3 digit

#7 03. 06. 2012 22:32

Re: Last 3 digit

#8 05. 06. 2012 06:28

Re: Last 3 digit

#9 06. 06. 2012 11:52

Re: Last 3 digit

Zápatí