It's almost prime

Number Theory Level 1

Find the remainder when $2^{340}$ is divided by $341$ .

The answer is 1.

2 solutions

Aditya Raut
Aug 1, 2014

$341= 11\times 31$

$2^5 = 32\equiv 1 \pmod{31} \implies 2^{340} \equiv 1 \pmod{31}$ .....(i)

Fermat's little theorem,

$2^{10} \equiv 1 \pmod{11} \implies 2^{340} \equiv 1 \pmod{11}$ .......(ii)

From (i) and (ii) , $2^{340}\equiv 1 \pmod{31\times 11}$

Hence answer is $\boxed{1}$

No idea of Fermet's theorem please provide some link or please explain it precisely..!!

Rahul Jain - 6 years, 10 months ago

It says that for any prime numeber $p$ ,for any integer $a$ such that $gcd(a,p)=1$ , we get that $a^{p-1} \equiv 1 \pmod{p}$ simple, that's Fermat's little theorem!

Aditya Raut - 6 years, 10 months ago

got it thanks..!!!

Rahul Jain - 6 years, 10 months ago

hey please elaborate it
is it possible to break 341 = 31*11 please explain it !!

Rishabh Jain - 6 years, 10 months ago

Fundamental proeperty, it is that if

$a\equiv b \pmod{c}$

And

$a\equiv b \pmod{d}$

Then

$a\equiv b \pmod{cd}$ , simple !

Aditya Raut - 6 years, 10 months ago

Know..wut? I just guessed it ...:P..Too tired to bash

Krishna Ar - 6 years, 10 months ago

I also just guessed!!!

Anuj Shikarkhane - 6 years, 10 months ago

Once you have seen that $2^5 \equiv 1 \pmod{31}$ and $2^{10} \equiv 1 \pmod{11}$ you know that $2^{10} \equiv 1 \pmod {341}$ so $2^{340} \equiv \left(2^{10}\right)^{34} \equiv 1 \pmod{341}$

Paolo Bentivenga - 6 years, 10 months ago

Thanks, updated.

Aditya Raut - 6 years, 10 months ago

thnx for updating

Nam Cao Vũ Hoàng - 6 years, 5 months ago

Mika Servi
Dec 10, 2014

341 divide 340 canot be so borrow 1 from 2 it will become 1. and the only no. left is 1

This solution is completely incorrect. What are you showing?

Sharky Kesa - 4 years, 4 months ago

It's almost prime

The answer is 1.

2 solutions

0 pending reports