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^{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.
\[\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
- 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^{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
-
- 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^{995-1}\equiv 1(mod\: 995)\]
$ a^{p-1} \equiv 1 (mod p)$ কিন্তু 995 prime না।
এক্ষেত্রে, $a^{\phi(n)} \equiv 1 (mod n)$ $a \perp n$
যদি এইটা বযবহার করতে হয় তাইলে, $ \phi(1990) = 792$