1 3 1 3 1 3
Find the last two digits of the number given above.
Bonus : Generalize this.
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.
Yes that would also work : How about my generelization ? @Otto Bretscher
Log in to reply
Well, we have p p p ≡ p p ( m o d 1 0 0 ) when p ≡ 1 ( m o d 4 ) and p p p ≡ p p − 1 otherwise (excluding 5 and 2). Beyond that, I don't think we can say much.
I hope I didn't disturb you... Can you please explain how to use carmichael lambda function ? in a short way ? @Otto Bretscher
Log in to reply
The Carmichael Lambda λ ( n ) is a way to strengthen Euler's Theorem, with very little "marginal cost", as economists say.
λ ( n ) is defines as the smallest positive integer m such that a m ≡ 1 ( m o d n ) whenever g cd ( a , n ) = 1 .
For odd prime powers n = p k we observe that λ ( p k ) = ϕ ( p k ) = p k − p k − 1 since the multiplicative group is cyclic. Also, λ ( 2 k ) = 2 k − 2 for k ≥ 3 .
The Carmichael lambda becomes useful when n has more than one prime power factor p k : While ϕ ( n ) is the product of the ϕ ( p k ) , we observe that λ ( n ) is the least common multiple of the λ ( p k ) . (This follows directly from the definition.)
For example, λ ( 1 0 0 0 ) = l c m ( λ ( 1 2 5 ) , λ ( 8 ) ) = l c m ( 1 0 0 , 2 ) = 1 0 0 .
Pretty simple stuff, really. If you do congruency problems without using Carmichael, it's like doing them with one hand tied to your back ;)
Carmichael's lambda function .
1 3 1 3 1 3 ( m o d 1 0 0 ) 1 3 ϕ ( 1 0 0 ) = 1 3 4 0 ≡ 1 ( m o d 1 0 0 ) ⇒ 1 3 1 3 ( m o d 4 0 ) ( 1 3 2 ) 6 ⋅ 1 3 ≡ ( 1 6 9 ) 6 ⋅ 1 3 ( m o d 4 0 ) 9 6 ⋅ 1 3 = 8 1 2 ⋅ 1 3 ≡ 1 3 ( m o d 4 0 ) ∴ 1 3 1 3 ( m o d 1 0 0 ) ( 1 3 3 ) 4 ⋅ 1 3 = ( 2 1 9 7 ) 4 ⋅ 1 3 ( m o d 1 0 0 ) ( − 3 ) 4 ⋅ 1 3 = 8 1 ⋅ 1 3 ≡ 5 3 ( m o d 1 0 0 )
Ah! That's a classic solution
Log in to reply
T H A N K S
Mine is the weirdest ! :P
what does mod 100 mean?
Log in to reply
mod 100 will give us the reminder when we divide that number with 100 ,i.e., the last two digits.
Slightly different method : Other than Euler's Theorem
For the tower , 1 3 1 3 1 3
Let upper 1 3 1 3 ≡ x m o d y , so 1 3 1 3 = y z + x for some z .
From here we get , 1 3 y z + x m o d 1 0 0 .
Let us assume that , 1 3 y ≡ 1 m o d 1 0 0 .
hence , 1 3 y z × 1 3 x ≡ 1 3 x m o d 1 0 0
So , 1 3 y = 1 0 0 p + 1 for some k . Note that numbet 1 3 y should end with 1 , which is only possible
when y = 4 a for some a .
So we arrive at , 1 3 4 a . z m o d 1 0 0 therefore 6 1 a ≡ 1 m o d 1 0 0 , it is clear that least value of a should be equal to 4
So y = 2 0 .
So , 1 3 1 3 ≡ x m o d 2 0 hence x = 1 3 .
Now the final congruence leads to , 1 3 1 3 m o d 1 0 0
and hence , 1 3 1 3 1 3 ≡ 5 3 m o d 1 0 0
Using Euler's Theorem we have 1 3 4 0 ≡ 1 ( m o d 1 0 0 )
And since 1 3 1 3 ≡ 1 3 ( m o d 4 0 ) , we have 1 3 1 3 1 3 = 1 3 4 0 x + 1 3 ≡ 1 ⋅ 1 3 1 3 ≡ 5 3 ( m o d 1 0 0 )
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 = 1 3 , 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 ≡ 6 1 m o d 1 0 0 , 1 3 8 ≡ 6 1 ∗ 6 1 ≡ 2 1 m o d 1 0 0 , 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 . ∴ 2 1 + 6 0 = 8 1 , ⟹ 1 3 1 2 ≡ 8 1 m o d 1 0 0 , ∴ 1 3 1 3 = 1 3 1 2 ∗ 1 3 = 8 1 ∗ 1 3 ≡ 5 3 m o d 1 0 0 , ∴ 8 1 + 6 0 = 1 4 1 , ⟹ 1 3 1 6 ≡ 4 1 m o d 1 0 0 , ∴ 4 1 + 6 0 = 1 0 1 , ⟹ 1 3 2 0 ≡ 0 1 m o d 1 0 0 , ⟹ 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 2 0 . ∴ 1 3 1 3 1 3 ≡ 1 3 5 3 ≡ 1 3 5 3 m o d 2 0 ≡ 1 3 1 3 ≡ 5 3 m o d 1 0 0 . 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 . 1 3 1 ≡ 1 3 m o d 1 0 0 1 3 2 ≡ 6 9 m o d 1 0 0 1 3 3 ≡ 9 7 m o d 1 0 0 1 3 4 ≡ 6 1 m o d 1 0 0 1 3 5 ≡ 9 3 m o d 1 0 0 1 3 6 ≡ 0 9 m o d 1 0 0 1 3 7 ≡ 1 7 m o d 1 0 0 1 3 8 ≡ 2 1 m o d 1 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ( + + ) 1 3 1 3 ≡ 5 3 m o d 1 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ( + + + + ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3 2 0 ≡ 0 1 m o d 1 0 0 ∴ 1 3 1 3 1 3 ≡ 1 3 5 3 ≡ 1 3 m o d 2 0 ≡ 1 3 1 3 ≡ 5 3 m o d 1 0 0 .
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.
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.
I used the fact that ( 2 m + 1 ) 2 0 n ≡ 0 1 ( m o d 1 0 0 ) , where n ∈ N , m ∈ N 0 , 5 ∤ 2 m + 1
By Euler's Theorem , we have 1 3 ϕ ( 2 0 ) ≡ 1 3 1 2 ≡ 1 ( m o d 2 0 )
⇒ 1 3 1 3 ≡ 1 3 1 2 × 1 3 ≡ 1 × 1 3 ≡ 1 3 ( m o d 2 0 )
∴ 1 3 1 3 1 3 ≡ 1 3 ( 2 0 n + 1 3 ) ≡ 1 3 2 0 n × 1 3 1 3 ≡ 1 3 1 3 ( m o d 1 0 0 ) .
1 3 1 3 ≡ ( 1 3 3 ) 4 × 1 3 ≡ ( 2 1 9 7 ) 4 × 1 3 ≡ ( − 3 ) 4 × 1 3 ≡ 8 1 × 1 3 ≡ 5 3 ( m o d 1 0 0 )
Our answer is 5 3
Why is the first line true?
(odd number) 2 0 n ≡ 1 ( m o d 1 0 0 ) is not quite right... it does not work for odd multiples of 5.
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...
Why is the first line true?
Log in to reply
By Euler’s Theorem , n 2 0 ≡ 1 ( m o d 2 5 ) where g c d ( n , 2 5 ) = 1
Hence all odd numbers other than multiples of 5 raised to the power 2 0 n give residue 1 when evaluated ( m o d 2 5 )
So the possible last two digits is equal are 0 1 , 2 6 , 5 1 , 7 6 .
Now 2 6 , 7 6 are not possible because unit digit cannot be even. Hence we are left to deal with the other two cases.
5 1 is also not possible because an odd perfect square is of the form 4 k + 1 .
So the only possibility is 0 1
Problem Loading...
Note Loading...
Set Loading...
We have λ ( 1 0 0 ) = 2 0 and λ ( 2 0 ) = 4 , where λ ( n ) represents the Carmichael Lambda . Thus 1 3 1 3 1 3 ≡ 1 3 1 3 ( m o d 1 0 0 ) since 1 3 ≡ 1 ( m o d 4 )
We observe that 1 3 3 ≡ − 3 ( m o d 1 0 0 ) so 1 3 1 2 ≡ 3 4 = 8 1 and 1 3 1 3 ≡ 1 3 × 8 1 ≡ 5 3