Compute 10^785 mod 23
1
Name:
Anonymous
2009-10-18 21:34
I don't want the solution right away but could someone please point me in the right direction? I know there must be some trick to somehow 'cancel' the huge exponent but I don't know how to play with it.
2
Name:
4tran
2009-10-19 0:52
3
Name:
Anonymous
2009-10-19 1:29
fermat/euler/lagrange and look at dat exposant
4
Name:
Anonymous
2009-10-19 20:44
So i get (10^22)^35 * 10^15
5
Name:
Anonymous
2009-10-20 3:21
you've been pointed in the right direction. Now gtfo.
6
Name:
4tran 2009-10-20 5:18
10^15 = 1000^5 = 11^5 (mod 23)... etc
7
Name:
Anonymous
2009-10-22 11:04
10785 = 10(23·34)+3 = 1023·34 · 10[sup] 3 = (1023 )34 3 23 mod 23 is 1 for all non-zero x. So:23 )34 3 = 1[sup] 34 · 103 = 103 mod 23 = 1000 mod 23 = 8
8
Name:
Anonymous
2009-10-22 11:05
Damn , I messed up the tags. Corrected version:785 = 10(23·34)+3 = 1023 ·34[/sup] · 10[sup] 3 = (1023 )34 3 23 mod 23 is 1 for all non-zero x. So:23 )34 3 = 134 · 103 = 103 mod 23 = 1000 mod 23 = 8
9
Name:
Anonymous
2009-10-22 11:07
Damn , I messed up the tags again . Final version (I hope! ):785 = 10(23·34)+3 = 1023·34 · 103 = (1023 )34 3 23 mod 23 is 1 for all non-zero x. So:23 )34 3 = 134 · 103 = 103 mod 23 = 1000 mod 23 = 8
10
Name:
4tran 2009-10-22 15:01
>>9
You made the same mistake I initially made; x
22 is 1 mod 23. The basic idea is the same; it just becomes a pain to compute. I think the final answer is 5 mod 23.
11
Name:
Anonymous
2009-10-25 17:53
12
Name:
Anonymous
2009-10-26 19:15
>>11
Somehow this made me sad. It's probably because I'm drunk.
13
Name:
Anonymous
2009-10-26 20:39
>>9
Wait, tex works again?? :D
I_{did_{not_{have_{sexual_{relations_{with_{the game}}}}}}}
14
Name:
Anonymous
2009-10-26 20:40