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.
3 solutions
sir, how did you multiply 2^4 in mod5^4
Log in to reply
If 2 2 0 0 0 ≡ 1 ( m o d 5 4 ) , then, multiplying everything with 2 4 , we can conclude that 2 2 0 0 4 ≡ 2 4 ( m o d 1 0 4 ) .
Log in to reply
i learn a new property. In general, a = b ( m o d n ) then a m = b m ( m o d n m ) ??
Log in to reply
@Dev Sharma – Yes, exactly: If a − b = k n for some integer k , then a m − b m = k n m
@Dev Sharma – This should be obvious by elementary modular arithmetic. If a , b , m , n be integers with m , n non-zero, then,
a ≡ b ( m o d n ) ⟺ ∃ q ∈ Z ∣ a − b = n q ⟺ a m − b m = n m q ⟺ n m ∣ a m − b m ⟺ a m ≡ b m ( m o d n m )
@Dev Sharma – How come a = b it should be a ≡ b Isn't it?
How did you simplify from 2^2016 to 2^16 in mod 10000? phi(10000) = 4000, not 2000, so what is the deal with it?
Log in to reply
He doesn't simplify there. Note that he establishes 2 2 0 0 4 ≡ 2 4 ( m o d 1 0 4 ) first. Multiply both sides of the congruence by 2 1 2 and you get 2 2 0 1 6 ≡ 2 1 6 ( m o d 1 0 4 ) .
Yay. New modular property
Note that the last 4 digits of 2 2 0 1 6 is just its remainder upon division by 1 0 0 0 0 . Thus, we have 2 2 0 1 6 = 4 1 0 0 8 = 1 6 5 0 4 = 2 5 6 2 5 2 ≡ 5 5 3 6 1 2 6 ≡ 7 2 9 6 6 3 ≡ 7 2 9 6 ⋅ 7 2 9 6 6 2 ≡ 7 2 9 6 ⋅ 1 6 1 6 3 1 ≡ ( 7 2 9 6 ⋅ 1 6 1 6 ) ⋅ 1 4 5 6 1 5 ≡ ( 3 3 6 ⋅ 1 4 5 6 ) ⋅ 9 9 3 6 7 ≡ ( 9 2 1 6 ⋅ 9 9 3 6 ) ⋅ 4 0 9 6 3 ≡ ( 1 7 6 ⋅ 4 0 9 6 ⋅ 7 2 1 6 ) ≡ 5 5 3 6 m o d 1 0 , 0 0 0
This is just the modular exponentiation algorithm.
Did same!!
Simply used Euler's Theorem.
this is not an explanation of how did you solve it
Using Euler's totient function, we have 2 5 0 0 ≡ 1 ( m o d 6 2 5 ) so 2 2 0 0 0 ≡ 1 ( m o d 5 4 ) . Multiplying through with 2 4 , we find 2 2 0 0 4 ≡ 2 4 ( m o d 1 0 4 ) . Finally 2 2 0 1 6 ≡ 2 1 6 = 6 5 5 3 6 ≡ 5 5 3 6 ( m o d 1 0 0 0 0 )