1. ## find the remainder

find the remainder when
2^1990 is divided by 1990..

plz explain the theorems involved in ur solution..

thanks

2. Originally Posted by ramanujam
find the remainder when
2^1990 is divided by 1990..

plz explain the theorems involved in ur solution..

thanks
$\displaystyle 2 \equiv 2 (\bmod 1990)$

$\displaystyle 2^{11} \equiv 2^{11} = -58 (\bmod 1990)$

$\displaystyle 2^{22} \equiv (-58)^2 = 3364 \equiv -616 (\bmod 1990)$

$\displaystyle 2^{44} \equiv (-616)^2 = 379456 \equiv -634 (\bmod 1990 )$

$\displaystyle 2^{88} \equiv (-634)^2 = -24 (\bmod 1990)$

$\displaystyle 2^{264} \equiv (-24)^3 = -13824 \equiv 106 (\bmod 1990)$

$\displaystyle 2^{528} \equiv (106)^2 = 11236 \equiv -704 (\bmod 1990 )$

$\displaystyle 2^{1056} \equiv (-704)^2 =495616 \equiv 106 (\bmod 1990)$

$\displaystyle 2^{1848}=2^{1056} \cdot 2^{528} \cdot 2^{264} \equiv 106 \cdot (-704) \cdot 106 \equiv 106 (\bmod 1990 )$

$\displaystyle 2^{1936} = 2^{1848}\cdot 2^{88}\equiv 106 \cdot (-24) \equiv -554 (\bmod 1990)$

$\displaystyle 2^{1980} = 2^{1936} \cdot 2^{44} = (-554)\cdot (-634) \equiv 996 (\bmod 1990)$

$\displaystyle 2^{1990} = 2^{1980}\cdot 2^{10} \equiv 996 \cdot 1024 \equiv 1024 (\mod 1990)$

3. ## second approach

Thanks perfect hacker..
a second approach to the problem would be
1990=2.5.199
we use euler's totient function here which states
for a prime ; this is because only the multiples of are not relatively prime to .
1990/2=5.199
hence
by using euler's totient theorem

or by using carmichael's theorem
we get

then
hence remainder when 2^1990 divided by 1990 is 1024

4. Originally Posted by ramanujam
Thanks perfect hacker..
a second approach to the problem would be
1990=2.5.199
That is a nicer approach. But there is a problem here. That approach is not your own! If you use someone else's idea at least say something like.

"On a different forum I recieved the following answer ...."

Than that would be okay, but not the way you did it!
And furthermore you dishonor Ramanajuan's name with such blashphemy

5. yes u right..
the approach is not mine..but i never said i had done it..
m sorry i forgot to mention where i got the second solution from..
i just thought i did share it with u..

i'll keep in mind to share from where and how i got my answer from now on..

Can anybody helpme out, how this last but one step..i.e.
2^1989 = 2^1989 - 5.396[1990/2]
i just can't understand this step...
@ThePerfectHacker,
can you explain...??

Thanks

Originally Posted by ramanujam
Thanks perfect hacker..
a second approach to the problem would be
1990=2.5.199
we use euler's totient function here which states
for a prime ; this is because only the multiples of are not relatively prime to .
1990/2=5.199
hence
by using euler's totient theorem

or by using carmichael's theorem
we get

then
hence remainder when 2^1990 divided by 1990 is 1024