The answer lies somewhere near the question?

If the remainder when 2 80 2^{80} is divided by 91 is A A , find A + 17 A+17 .


The answer is 91.

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.

2 solutions

Note that 4096 = 2 12 1 ( m o d 91 ) 4096={ 2 }^{ 12 }\equiv 1(mod\quad 91) , then 2 80 = ( 2 12 ) 6 2 8 1 6 256 ( m o d 91 ) { 2 }^{ 80 }={ ({ 2 }^{ 12 }) }^{ 6 }\cdot { 2 }^{ 8 }\equiv { 1 }^{ 6 }\cdot 256(mod\quad 91) , thus, 2 80 74 ( m o d 91 ) { 2 }^{ 80 }\equiv 74(mod\quad 91) , and the desired answer is 91.

Puneet Pinku
May 24, 2016

Relevant wiki: Euler's Theorem

Since (2,91) = 1, we can apply Euler's Theorem,

a φ ( p ) 1 a^{\varphi(p)} \equiv 1 mod p, where a & p are coprimes.

2 φ ( 91 ) 1 2^{\varphi(91)} \equiv 1 mod 91

2 72 1 \Rightarrow 2^{72} \equiv 1 mod 91 ............(1) (since φ ( 91 ) = 91 × 12 13 × 6 7 = 72 \varphi(91) = 91\times\frac{12}{13} \times \frac{6}{7} = 72 )

Now we know that 2 8 2^{8} \equiv 74 mod 91 ................(2)

Multiplying (1) & (2), we get

2 80 2^{80} \equiv 74 mod 91. Hence, the remainder is 74. Adding 17 to it, we get 91 \boxed{91} as our answer.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...