Find the remainder
Find the remainder
What is the remainder when 2^1990 divided by 1990?
Re: Find the remainder
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
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
Re: Find the remainder
My soln was
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
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
Re: Find the remainder
Please explain your solution.Labib wrote:My soln was
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)
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)
 Cryptic.shohag
 Posts: 16
 Joined: Fri Dec 17, 2010 11:32 pm
 Location: Dhaka, Bangladesh
 Contact:
Re: Find the remainder
\[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^{9951}\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.
\[\Rightarrow 995=5\times 199\]:
\[So,\: 2\: is\: a\: coprime\: to\: 995.\: According\: to\: Fermat's\: theorem,\]
\[\Rightarrow 2^{9951}\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
 Cryptic.shohag
 Posts: 16
 Joined: Fri Dec 17, 2010 11:32 pm
 Location: Dhaka, Bangladesh
 Contact:
Re: Find the remainder
\[1990=2\times 5\times 199\]protik wrote:What is the remainder when 2^1990 divided by 1990?
\[\Rightarrow 995=5\times 199\]:
\[So,\: 2\: is\: a\: coprime\: to\: 995.\: According\: to\: Fermat's\: theorem,\]
\[\Rightarrow 2^{9951}\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

 Posts: 125
 Joined: Mon Dec 13, 2010 12:05 pm
 Location: চট্রগ্রাম,Chittagong
 Contact:
Re: Find the remainder
Fermat's theorem \[\Rightarrow\]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^{9951}\equiv 1(mod\: 995)\]
$ a^{p1} \equiv 1 (mod p)$ কিন্তু 995 prime না।
এক্ষেত্রে, $a^{\phi(n)} \equiv 1 (mod n)$ $a \perp n$
যদি এইটা বযবহার করতে হয় তাইলে, $ \phi(1990) = 792$