Prime tower

1 3 1 3 13 \Large 13^{13^{13}}

Find the last two digits of the number given above.

Bonus : Generalize this.


You may also try Mod-Ladder .


The answer is 53.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

6 solutions

Otto Bretscher
Mar 8, 2016

We have λ ( 100 ) = 20 \lambda(100)=20 and λ ( 20 ) = 4 \lambda(20)=4 , where λ ( n ) \lambda(n) represents the Carmichael Lambda . Thus 1 3 1 3 13 1 3 13 ( m o d 100 ) 13^{13^{13}}\equiv 13^{13} \pmod{100} since 13 1 ( m o d 4 ) 13\equiv 1 \pmod{4}

We observe that 1 3 3 3 ( m o d 100 ) 13^3\equiv -3 \pmod{100} so 1 3 12 3 4 = 81 13^{12}\equiv 3^4=81 and 1 3 13 13 × 81 53 13^{13}\equiv 13\times 81\equiv \boxed{53}

Yes that would also work : How about my generelization ? @Otto Bretscher

A Former Brilliant Member - 5 years, 3 months ago

Log in to reply

Well, we have p p p p p ( m o d 100 ) p^{p^p}\equiv p^p \pmod{100} when p 1 ( m o d 4 ) p\equiv 1 \pmod{4} and p p p p p 1 p^{p^p}\equiv p^{p^{-1}} otherwise (excluding 5 and 2). Beyond that, I don't think we can say much.

Otto Bretscher - 5 years, 3 months ago

I hope I didn't disturb you... Can you please explain how to use carmichael lambda function ? in a short way ? @Otto Bretscher

A Former Brilliant Member - 5 years, 3 months ago

Log in to reply

The Carmichael Lambda λ ( n ) \lambda(n) is a way to strengthen Euler's Theorem, with very little "marginal cost", as economists say.

λ ( n ) \lambda(n) is defines as the smallest positive integer m m such that a m 1 ( m o d n ) a^m\equiv 1 \pmod{n} whenever gcd ( a , n ) = 1 \gcd(a,n)=1 .

For odd prime powers n = p k n=p^k we observe that λ ( p k ) = ϕ ( p k ) = p k p k 1 \lambda(p^k)=\phi(p^k)=p^k-p^{k-1} since the multiplicative group is cyclic. Also, λ ( 2 k ) = 2 k 2 \lambda(2^k)=2^{k-2} for k 3 k\geq 3 .

The Carmichael lambda becomes useful when n n has more than one prime power factor p k p^k : While ϕ ( n ) \phi(n) is the product of the ϕ ( p k ) \phi(p^k) , we observe that λ ( n ) \lambda(n) is the least common multiple of the λ ( p k ) \lambda(p^k) . (This follows directly from the definition.)

For example, λ ( 1000 ) = l c m ( λ ( 125 ) , λ ( 8 ) ) = l c m ( 100 , 2 ) = 100 \lambda(1000)=lcm(\lambda(125),\lambda(8))=lcm(100,2)=100 .

Pretty simple stuff, really. If you do congruency problems without using Carmichael, it's like doing them with one hand tied to your back ;)

Otto Bretscher - 5 years, 3 months ago
Akshat Sharda
Mar 8, 2016

1 3 1 3 13 ( m o d 100 ) 1 3 ϕ ( 100 ) = 1 3 40 1 ( m o d 100 ) 1 3 13 ( m o d 40 ) ( 1 3 2 ) 6 13 ( 169 ) 6 13 ( m o d 40 ) 9 6 13 = 8 1 2 13 13 ( m o d 40 ) 1 3 13 ( m o d 100 ) ( 1 3 3 ) 4 13 = ( 2197 ) 4 13 ( m o d 100 ) ( 3 ) 4 13 = 81 13 53 ( m o d 100 ) 13^{13^{13}} \pmod {100} \\ 13^{\phi(100)}=13^{40} \equiv 1 \pmod {100} \\ \Rightarrow 13^{13} \pmod {40} \\ (13^2)^6\cdot 13 \equiv (169)^{6}\cdot 13 \pmod {40} \\ 9^6\cdot 13 = 81^2\cdot 13\equiv 13 \pmod {40} \\ \therefore 13^{13} \pmod {100} \\ (13^3)^4\cdot 13 =(2197)^4\cdot 13 \pmod {100} \\ (-3)^4\cdot 13=81\cdot 13\equiv \boxed{53} \pmod {100}

Ah! That's a classic solution

Department 8 - 5 years, 3 months ago

Log in to reply

T H A N K S \mathcal{THANKS}

Akshat Sharda - 5 years, 3 months ago

Mine is the weirdest ! :P

A Former Brilliant Member - 5 years, 3 months ago

what does mod 100 mean?

Zain Malik - 5 years, 3 months ago

Log in to reply

mod 100 will give us the reminder when we divide that number with 100 ,i.e., the last two digits.

Akshat Sharda - 5 years, 3 months ago

Slightly different method : Other than Euler's Theorem

For the tower , 1 3 1 3 13 13^{13^{13}}

Let upper 1 3 13 x m o d y 13^{13} \equiv x \mod y , so 1 3 13 = y z + x 13^{13}=yz+x for some z z .

From here we get , 1 3 y z + x m o d 100 13^{yz+x} \mod 100 .

Let us assume that , 1 3 y 1 m o d 100 13^y \equiv 1 \mod 100 .

hence , 1 3 y z × 1 3 x 1 3 x m o d 100 13^{yz} × 13^x \equiv 13^x \mod 100

So , 1 3 y = 100 p + 1 13^y=100p+1 for some k k . Note that numbet 1 3 y 13^y should end with 1 , which is only possible

when y = 4 a y=4a for some a a .

So we arrive at , 1 3 4 a . z m o d 100 13^{4a . z}\mod 100 therefore 6 1 a 1 m o d 100 61^a\equiv 1 \mod 100 , it is clear that least value of a a should be equal to 4

So y = 20 y=20 .

So , 1 3 13 x m o d 20 13^{13}\equiv x \mod 20 hence x = 13 x=13 .

Now the final congruence leads to , 1 3 13 m o d 100 13^{13} \mod 100

and hence , 1 3 1 3 13 53 m o d 100 13^{13^{13}} \equiv 53 \mod 100

William Isoroku
Mar 9, 2016

Using Euler's Theorem we have 1 3 40 1 ( m o d 100 ) 13^{ 40 }\equiv 1 (\mod{100})

And since 1 3 13 13 ( m o d 40 ) 13^{ 13 }\equiv 13 (\mod{40}) , we have 1 3 13 13 = 1 3 40 x + 13 1 13 13 53 ( m o d 100 ) 13^{ { 13 }^{ 13 } }=13^{ 40x+13 }\equiv 1\cdot { 13 }^{ 13 }\equiv 53 (\mod{100})

3 m i s c y c l i c , p e r i o d 4. m n m o d 4. T h e n f o r n = 1 , 2 , 3 , 4 , l a s t d i g i t o f 3 m = 3 , 9 , 7 , 1. m = 13 , s o n = 3. Last two digit will complete a cycle when they are 01. So end of every 4th (n=4) term starting from exponent 1 is investigated. 1 3 4 61 m o d 100 , 1 3 8 61 61 21 m o d 100 , T h e t e n t h d i g i t i s i n c r e a s e d b y 6. 21 + 60 = 81 , 1 3 12 81 m o d 100 , 1 3 13 = 1 3 12 13 = 81 13 53 m o d 100 , 81 + 60 = 141 , 1 3 16 41 m o d 100 , 41 + 60 = 101 , 1 3 20 01 m o d 100 , T h e c y c l e f o r l a s t t w o d i g i t i s 20. 1 3 1 3 13 1 3 53 1 3 53 m o d 20 1 3 13 53 m o d 100. B e l o w s a m e i s w o r k e d o u t i n t a b u l a r f o r m . 3^m~ is~ cyclic,~ period~ 4.~ m\ \equiv~ n~ mod~ 4.~~ Then~ for~ ~n~=~1,~ 2,~ 3,~ 4,~ last~ digit~ of~ 3^m ~= ~3,~ 9, ~7,~ 1.\\ m=13, ~so~ n~= 3.\\ \text{Last two digit will complete a cycle when they are 01.}\\ \text{ So end of every 4th (n=4) term starting from exponent 1 is investigated.}\\ 13^4\ \equiv~{\Large 61} ~ mod~ 100, \\ 13^8\ \equiv~ 61*61\ \equiv~{\Large 21} ~ mod~ 100, \\ ~~~~The~ tenth~ digit~ is ~increased~ by~6.\\ \therefore~21+60=81,~\implies~13^{12}\ \equiv~{\Large 81} ~ mod~ 100, \\ \therefore~\color{#E81990}{13^{13}=13^{12}*13=81*13 \equiv~{\Large 53} ~ mod~ 100,} \\ \therefore~81+60=141,~\implies~13^{16}\ \equiv~{\Large 41} ~ mod~ 100, \\ \therefore~41+60=101,~\implies~13^{20}\ \equiv~{\Huge 01} ~mod~ 100, \\ \implies~The~cycle~for~last~two~digit~is~~20. \\ \therefore\ \Large 13^{13^{13}}\ \equiv\ 13^{53}\ \equiv\ 13^{{53}\ mod\ 20} \equiv~13^{13}\ \equiv~{\Huge 53} ~ mod~ 100.\\ Below~same~is~worked~out~in~tabular~form. \\ 1 3 1 13 m o d 100 1 3 2 69 m o d 100 1 3 3 97 m o d 100 1 3 4 61 m o d 100 1 3 5 93 m o d 100 1 3 6 09 m o d 100 1 3 7 17 m o d 100 1 3 8 21 m o d 100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ( + + ) 1 3 13 53 m o d 100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ( + + + + ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3 20 01 m o d 100 1 3 1 3 13 1 3 53 13 m o d 20 1 3 13 53 m o d 100. \color{#20A900} {13^1 \equiv~13 ~ mod~ 100\ \ \ \ \ \ \ \ 13^2 \equiv~69 ~ mod~ 100 \ \ \ \ \ \ \ \ 13^3 \equiv~97 ~ mod~ 100\ \ \ \ \ \ 13^4\ \equiv~61 ~ mod~ 100 \\ 13^5 \equiv~93 ~ mod~ 100\ \ \ \ \ \ \ \ 13^6 \equiv~09 ~ mod~ 100 \ \ \ \ \ \ \ \ 13^7 \equiv~17 ~ mod~ 100\ \ \ \ \ \ 13^8\ \equiv~21 ~ mod~ 100 } \\ ................................................................................ .... (++) \\ {\color{#D61F06}{13^{13} \equiv~53 ~ mod~ 100 } } ................................................................... (++++) \\ .................................................................. 13^{\color{#20A900}{20} } \equiv~01 ~ mod~ 100 \\ \therefore\ \Large 13^{13^{13}}\ \equiv\ 13^{{53}\ \ \equiv\ 13\ mod\ 20} \equiv~13^{13}\ \equiv~{\Huge 53} ~ mod~ 100.

Note:-
( + + ) 1st column tenth digit increment is 8, for 4th, it is 6. So for exponent 13, 1st column unit digit is 3. last one of tenth digit,=(1+3*8)=15 ( + + + + ) So for last digits to be 01, with tenth digit increment of 6, exponent is 20. (++)\color{#E81990}{ \text{ 1st column tenth digit increment is 8, for 4th, it is 6.} \\ \text{ So for exponent 13, 1st column unit digit is 3. last one of tenth digit,=(1+3*8)=15 }\\ (++++) \text{So for last digits to be 01, with tenth digit increment of 6, exponent is 20.} }\\
You may refer to my note in the solution of hard problem " Mod-Ladder" by Chinmay Sangawadekar for the logic of my above solution. The method can solve TOWER problem with the help only of a simple scientific calculator and no knowledge of Theory of Numbers.

Ankit Kumar Jain
Mar 8, 2016

I used the fact that ( 2 m + 1 ) 20 n 01 ( m o d 100 ) {(2m + 1)^{20n}}\equiv{01}\pmod{100} , where n N , m N 0 , 5 2 m + 1 n \in N , m \in N_0 , 5\nmid 2m + 1

By Euler's Theorem , we have 1 3 ϕ ( 20 ) 1 3 12 1 ( m o d 20 ) 13^{\phi(20)}\equiv{13^{12}}\equiv{1}\pmod{20}

1 3 13 1 3 12 × 13 1 × 13 13 ( m o d 20 ) \Rightarrow 13^{13}\equiv13^{12}\times{13}\equiv1\times{13}\equiv13\pmod{20}

1 3 1 3 13 1 3 ( 20 n + 13 ) 1 3 20 n × 1 3 13 1 3 13 ( m o d 100 ) \therefore 13^{13^{13}}\equiv {13^{(20n + 13)}}\equiv{13^{20n}\times{13^{13}}}\equiv{13^{13}}\pmod{100} .

1 3 13 ( 1 3 3 ) 4 × 13 ( 2197 ) 4 × 13 ( 3 ) 4 × 13 81 × 13 53 ( m o d 100 ) 13^{13}\equiv(13^{3})^{4}\times{13}\equiv(2197)^{4}\times{13}\equiv(-3)^{4}\times{13}\equiv{81}\times{13}\equiv{53}\pmod{100}

Our answer is 53 \boxed{53}

Moderator note:

Why is the first line true?

(odd number) 20 n 1 ( m o d 100 ) ^{20n}\equiv 1\pmod{100} is not quite right... it does not work for odd multiples of 5.

Otto Bretscher - 5 years, 3 months ago

Log in to reply

Oh I am sorry sir I forgot to mention that in my solution.

Let me do it right now...BTW thanks for pointing out...

Ankit Kumar Jain - 5 years, 3 months ago

Why is the first line true?

Calvin Lin Staff - 5 years, 3 months ago

Log in to reply

@Calvin Lin

By Euler’s Theorem \text{Euler's Theorem} , n 20 1 ( m o d 25 ) n^{20} \equiv{1}\pmod{25} where g c d ( n , 25 ) = 1 gcd (n , 25) = 1

Hence all odd numbers other than multiples of 5 5 raised to the power 20 n 20n give residue 1 1 when evaluated ( m o d 25 ) \pmod{25}

So the possible last two digits is equal are 01 , 26 , 51 , 76 01 , 26 , 51 , 76 .

Now 26 , 76 26 , 76 are not possible because unit digit cannot be even. Hence we are left to deal with the other two cases.

51 51 is also not possible because an odd perfect square is of the form 4 k + 1 4k + 1 .

So the only possibility is 01 \boxed{01}

Ankit Kumar Jain - 5 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...