Euler could have easily solved it!

Find the remainder when 3 2016 + 6 2016 3^{2016}+6^{2016} is divided by 49?


The answer is 2.

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.

1 solution

Alex G
May 11, 2016

Relevant wiki: Euler's Totient Function

Calculating ϕ ( 49 ) \phi{(49)} :

ϕ ( 49 ) = 49 ( 1 1 7 ) = 42 \phi{(49)} = 49 \left(1-\dfrac{1}{7}\right) = 42

Rewriting the problem:

( 3 48 ) 42 + ( 6 48 ) 42 {(3^{48})}^{42}+{(6^{48})}^{42}

Using Euler's Totient Theorem, a ϕ ( n ) 1 m o d n a^{\phi(n)} \equiv 1 \mod n :

1 + 1 m o d 42 1+1 \mod 42

2 \boxed 2

Absolutely correct!!

Puneet Pinku - 5 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...