Is it a Multiple?

Is 2 150 1 2^{150} - 1 a multiple of 31? Note that 31 is prime.

Yes No No way to tell

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.

3 solutions

Otto Bretscher
Dec 23, 2018

2 150 = ( 2 5 ) 30 = 3 2 30 1 30 = 1 ( m o d 31 ) 2^{150}=(2^5)^{30}=32^{30}\equiv 1^{30}=1 \pmod{31} ; the answer is Y e s \boxed{Yes}

Chew-Seong Cheong
Dec 23, 2018

It can also be solved using Euler's theorem as follows:

2 150 1 2 150 m o d ϕ ( 31 ) 1 (mod 31) Since gcd ( 2 , 31 ) = 1 , Euler’s theorem applies. 2 150 m o d 30 1 (mod 31) Euler’s totient function ϕ ( 31 ) = 31 1 = 30 2 0 1 (mod 31) 0 (mod 31) \begin{aligned} 2^{150} - 1 & \equiv 2^{\color{#3D99F6} 150 \bmod \phi(31)} - 1 \text{ (mod 31)} & \small \color{#3D99F6} \text{Since }\gcd(2,31) = 1 \text{, Euler's theorem applies.} \\ & \equiv 2^{\color{#3D99F6} 150 \bmod 30} - 1 \text{ (mod 31)} & \small \color{#3D99F6} \text{Euler's totient function }\phi(31) = 31-1 = 30 \\ & \equiv 2^{\color{#3D99F6} 0} - 1 \text{ (mod 31)} \\ & \equiv \boxed 0 \text{ (mod 31)} \end{aligned}

Yes , 31 2 150 1 31 \mid 2^{150}-1

William Allen
Dec 23, 2018

2 150 1 ( m o d 31 ) 2^{150}\equiv 1\pmod{31}

( 2 30 ) 5 1 ( m o d 31 ) \Rightarrow (2^{30})^5\equiv 1\pmod{31} and 2 30 1 ( m o d 31 ) 2^{30}\equiv 1\pmod{31} by Fermat’s Little Theorem.

( 2 30 ) 5 1 ( m o d 31 ) = 1 5 1 ( m o d 31 ) = 2 150 1 ( m o d 31 ) \Rightarrow (2^{30})^5\equiv 1\pmod{31} = 1^5\equiv 1\pmod{31} = 2^{150}\equiv 1\pmod{31}

31 2 150 1 \Rightarrow 31 \vert 2^{150}-1

Y e s \Rightarrow \boxed{Yes} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...