## Find the remainder

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

### Find the remainder

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

Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm

### 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

Labib
Posts: 411
Joined: Thu Dec 09, 2010 10:58 pm

### 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

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

### Re: Find the remainder

Labib wrote:My soln was
Every logical solution to a problem has its own beauty.

jagdish
Posts: 38
Joined: Wed Jan 19, 2011 2:21 pm

### Re: Find the remainder

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

Cryptic.shohag
Posts: 16
Joined: Fri Dec 17, 2010 11:32 pm
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.
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
Contact:

### Re: Find the remainder

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

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$