Determine the remainder when 1 4 1 4 1 4 1 4 is divided by 1 2 5 .
Details and assumptions
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.
Latex Would have made your solution better. Good problem Golechha , tricked me at the end! :(
Log in to reply
@Krishna Ar I like being called Satvik, or SG for a nickname, BTW I'll try to Latex-ify the solution, thanks.. :D
Log in to reply
Sorry if you didnt like it :P
Log in to reply
@Krishna Ar – I've latexed your solution, @Abi Krishnan . You may also learn latex on the net. It's quite easy to learn and is very useful.
Up-voted! ..
You could not have used the same principle again since g cd ( 1 4 , 1 0 0 ) = 2 = 1 . I used the Chinese Remainder Theorem for this (continued the way the last line of your solution says). There isn't a better way than this.
Log in to reply
Exactly. That's why I added that last line.
Log in to reply
You? It's Abi Krishnan.. Do you have 2 accounts?
Log in to reply
@Mathh Mathh – No, I'm one of the moderators.
Log in to reply
@Satvik Golechha – ohh my bad, I did not see that, good thing it gave the right answer though
You say that a ϕ ( m ) ≡ 1 ( m o d m ) for all a coprime to m . But then you say that 1 4 X ≡ 1 4 x m o d ϕ ( 1 2 5 ) ( m o d 1 2 5 ) . ϕ ( 1 2 5 ) = 1 0 0 . Why isn't it 1 4 ϕ ( 1 2 5 ) ≡ 1 ( m o d 1 2 5 ) ?
wolfram lol
Problem Loading...
Note Loading...
Set Loading...
ϕ ( x ) denotes the number of positive integers less that and coprime to x .
a ϕ ( m ) ≡ 1 ( m o d m ) for all a coprime to m . So 1 4 x ≡ 1 4 x m o d ϕ ( 1 2 5 ) ( m o d 1 2 5 ) . ϕ ( 1 2 5 ) = 1 0 0 .
x in this case is 1 4 1 4 1 4 . We only care what 1 4 1 4 1 4 is in modulo 1 0 0 to solve this problem.
We can use the same principle as above to find what 1 4 1 4 is in modulo ϕ ( 1 0 0 ) = 4 0 , and 4 1 4 ≡ 1 6 ( m o d 4 0 ) . To find x m o d 1 0 0 , we need to thus find 1 4 1 6 ( m o d 1 0 0 ) , which is 3 6 . So 1 4 x is the same as 1 4 3 6 ( m o d 1 2 5 ) , so we get remainder as 8 6 .
We can also find 1 4 1 4 1 4 ( m o d 1 0 0 ) by finding 1 4 1 4 1 4 ( m o d 2 5 ) and 1 4 1 4 1 4 ( m o d 4 ) , and then using the Chinese Remainder Theorem.