Remainders are fun

Find the remainder when 2 8 45 28^{45} is divided by 45.


The answer is 28.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Chew-Seong Cheong
May 13, 2015

We note that 2 8 4 = 614656 1 ( m o d 45 ) \space 28^4 = 614656 \equiv 1 \pmod{45} .

2 8 45 2 8 4 × 10 + 1 ( m o d 45 ) 28 ( 2 8 4 ) 10 ( m o d 45 ) 28 ( m o d 45 ) \Rightarrow 28^{45} \equiv 28^{4\times 10+1} \pmod{45} \equiv 28 \left( 28^4 \right)^{10} \pmod{45} \equiv \boxed{28} \pmod{45}

Sir, This is the approach I used.

We know that:- a p 1 1 ( m o d p ) {a}^{p-1} \equiv 1\pmod{p}

Hence, 28 44 1 ( m o d 45 ) {28}^{44} \equiv 1\pmod {45}

Thus, Multiplying both sides By 28, We get the remainder to be 28 :)

Mehul Arora - 6 years, 1 month ago

Log in to reply

You got lucky; Fermat's little theorem is only guaranteed for p prime.

Harrison Wang - 6 years, 1 month ago

Log in to reply

Ohh yeah. I got lucky. Really.Sometimes you tend to overlook basic things When you practice higher level mathematics :3 XD. Thanks for clearing my doubt! @Harrison Wang

Mehul Arora - 6 years, 1 month ago
Sarthak Rath
May 13, 2015

2 8 2 19 ( m o d 45 ) 28^2 \equiv 19 \pmod{45}

2 8 3 37 ( m o d 45 ) 28^3 \equiv 37 \pmod{45}

2 8 5 28 ( m o d 45 ) 28^5 \equiv 28 \pmod{45} from first two.

2 8 10 19 ( m o d 45 ) 28^{10} \equiv 19 \pmod{45}

2 8 20 1 ( m o d 45 ) 28^{20} \equiv 1 \pmod{45}

2 8 40 1 ( m o d 45 ) 28^{40} \equiv 1 \pmod{45}

2 8 45 28 ( m o d 45 ) 28^{45} \equiv 28 \pmod{45} from equation (3) and (6)

hence the answer is 28 \boxed{28}

Mas Mus
May 30, 2015

Since g c d ( 28 , 45 ) = 1 gcd(28, 45)=1 , we can use Euler's Theorem . We know that ϕ ( 45 ) = 24 \phi(45)=24 .

28 45 ( 28 ) 2 × ϕ ( 45 ) × 28 1 × 28 28 ( m o d 45 ) {28}^{45}\equiv(28)^{2\times{\phi(45)}}\times{28}\equiv1\times{28}\equiv28\pmod{45}

i don't understand, because 2 x 24 is 48, and still multiplied again by 28 becomes 28^49 ... ?

de azalea - 4 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...