Find the remainder

For discussing Olympiad Level Number Theory problems
protik
Posts:35
Joined:Wed Dec 08, 2010 7:21 am
Find the remainder

Unread post by protik » Wed Dec 29, 2010 8:10 pm

What is the remainder when 2^1990 divided by 1990?

User avatar
Labib
Posts:411
Joined:Thu Dec 09, 2010 10:58 pm
Location:Dhaka, Bangladesh.

Re: Find the remainder

Unread post by Labib » Wed Dec 29, 2010 11:53 pm

Protik, could ya verify my proof posting it over here?? plzzzz....
Please Install $L^AT_EX$ fonts in your PC for better looking equations,
Learn how to write equations, and don't forget to read Forum Guide and Rules.


"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." - Sherlock Holmes

User avatar
Labib
Posts:411
Joined:Thu Dec 09, 2010 10:58 pm
Location:Dhaka, Bangladesh.

Re: Find the remainder

Unread post by Labib » Wed Dec 29, 2010 11:56 pm

My soln was
$1024$
Please Install $L^AT_EX$ fonts in your PC for better looking equations,
Learn how to write equations, and don't forget to read Forum Guide and Rules.


"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." - Sherlock Holmes

User avatar
Zzzz
Posts:172
Joined:Tue Dec 07, 2010 6:28 am
Location:22° 48' 0" N / 89° 33' 0" E

Re: Find the remainder

Unread post by Zzzz » Fri Jan 07, 2011 7:18 am

Labib wrote:My soln was
$1024$
Please explain your solution.
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

jagdish
Posts:38
Joined:Wed Jan 19, 2011 2:21 pm
Location:India (Himanchal Pradesh)

Re: Find the remainder

Unread post by jagdish » Thu Jan 27, 2011 10:59 pm

Can we solve using this by binomial theorem........
jagdish

User avatar
Cryptic.shohag
Posts:16
Joined:Fri Dec 17, 2010 11:32 pm
Location:Dhaka, Bangladesh
Contact:

Re: Find the remainder

Unread post by Cryptic.shohag » Sun Feb 06, 2011 12:09 am

\[1990=2\times 5\times 199\]
\[\Rightarrow 995=5\times 199\]:

\[So,\: 2\: is\: a\: coprime\: to\: 995.\: According\: to\: Fermat's\: theorem,\]

\[\Rightarrow 2^{995-1}\equiv 1(mod\: 995)\]
\[\Rightarrow (2^{994})^2\equiv 1^2(mod\: 995)\]
\[\Rightarrow 2^{1988}\equiv 1(mod\: 995)\]
\[\Rightarrow 2^{1988}\times 4\equiv 1\times 4(mod\: 995\times 4)\]
\[\Rightarrow 2^{1990}\equiv 4(mod\: 1990\times 2)\]
\[\Rightarrow 2^{1990}\equiv 4(mod\: 1990)\]

So, the remainder is 4. :)
God does not care about our mathematical difficulties; He integrates empirically. ~Albert Einstein

User avatar
Cryptic.shohag
Posts:16
Joined:Fri Dec 17, 2010 11:32 pm
Location:Dhaka, Bangladesh
Contact:

Re: Find the remainder

Unread post by Cryptic.shohag » Sun Feb 06, 2011 12:13 am

protik wrote:What is the remainder when 2^1990 divided by 1990?
\[1990=2\times 5\times 199\]
\[\Rightarrow 995=5\times 199\]:

\[So,\: 2\: is\: a\: coprime\: to\: 995.\: According\: to\: Fermat's\: theorem,\]

\[\Rightarrow 2^{995-1}\equiv 1(mod\: 995)\]
\[\Rightarrow (2^{994})^2\equiv 1^2(mod\: 995)\]
\[\Rightarrow 2^{1988}\equiv 1(mod\: 995)\]
\[\Rightarrow 2^{1988}\times 4\equiv 1\times 4(mod\: 995\times 4)\]
\[\Rightarrow 2^{1990}\equiv 4(mod\: 1990\times 2)\]
\[\Rightarrow 2^{1990}\equiv 4(mod\: 1990)\]

So, the remainder is 4. :)
God does not care about our mathematical difficulties; He integrates empirically. ~Albert Einstein

AntiviruShahriar
Posts:125
Joined:Mon Dec 13, 2010 12:05 pm
Location:চট্রগ্রাম,Chittagong
Contact:

Re: Find the remainder

Unread post by AntiviruShahriar » Thu Mar 10, 2011 12:22 pm

Cryptic.shohag wrote: \[1990=2\times 5\times 199\]
\[\Rightarrow 995=5\times 199\]:

\[So,\: 2\: is\: a\: coprime\: to\: 995.\: According\: to\: Fermat's\: theorem,\]

\[\Rightarrow 2^{995-1}\equiv 1(mod\: 995)\]
Fermat's theorem \[\Rightarrow\]
$ a^{p-1} \equiv 1 (mod p)$ কিন্তু 995 prime না।
এক্ষেত্রে, $a^{\phi(n)} \equiv 1 (mod n)$ $a \perp n$
যদি এইটা বযবহার করতে হয় তাইলে, $ \phi(1990) = 792$

Post Reply