R.I.P. Calculators!

Number Theory Level 3

Find the GCD of $({\color{#D61F06} {3}}^{625}-1)$ , $({\color{#3D99F6} {9}}^{200}-1)$ and $({\color{#20A900} {81}}^{25}-1)$ .

Notation : $\gcd(\cdot)$ denotes the greatest common divisor function.

{3}^{100}-{3}^{5}

{3}^{25}-1

{3}^{5}-3

GCD not possible.

{3}^{125}-{3}^{25}

Cannot be determined

1 solution

Swapnil Das
Jun 14, 2016

Fast algorithm : $\large \text{gcd}({ a }^{ x }-1,{ a }^{ y }-1,{ a }^{ z }-1)=({ a }^{\text{ gcd}(x,y,z) }-1)$ .

$\therefore$ $\text{gcd}({ 3 }^{ 625 }-1,{ 3 }^{ 400 }-1,{ 3 }^{ 100 }-1)=({ 3 }^{\text{ gcd}(625,400,100) }-1)={ 3 }^{ 25 }-1$ .

Great.! (+1)

Abhay Tiwari - 5 years ago

same method...............

Abhisek Mohanty - 4 years, 12 months ago

Or directly check the largest power of 3 which divides all powers 😂😂😂😂😂;);():P

A Former Brilliant Member - 4 years, 12 months ago