A number theory problem by Paola Ramírez

Number Theory Level 4

gcd ⁡ ( 2 100 − 1 , 2 120 − 1 ) = ? \large \gcd(2^{100}-1,2^{120}-1) = \, ?

Clarification : gcd ⁡ ( ⋅ ) \gcd(\cdot) denotes the greatest common divisor function.


The answer is 1048575.

Paola Ramírez by Paola Ramírez , 24, Mexico

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

Ankit Nigam
Apr 30, 2016

An important result:- gcd ⁡ ( a m − 1 , a n − 1 ) = a gcd ⁡ ( m , n ) − 1 \gcd(a^m - 1, a^n - 1) = a^{\gcd(m, n)} - 1

∴ gcd ⁡ ( 2 100 − 1 , 2 120 − 1 ) = 2 gcd ⁡ ( 100 , 120 ) − 1 = 2 20 − 1 = 1048575 \therefore \gcd(2^{100} - 1, 2^{120} - 1) = 2^{\gcd(100, 120) }- 1 = 2^{20} - 1 = 1048575

7 Helpful 1 Interesting 0 Brilliant 0 Confused

Could you demonstrate the important result?

Paola Ramírez - 5 years, 1 month ago

Log in to reply

I do not have enough time to write whole LaTeX, so i am posting image of proof. Image has been added to my solution :)

Ankit Nigam - 5 years, 1 month ago

The exactly same question appeared NTSE ANDHRA PRADESH in mathematics section. Q152. What a coincidence.

Puneet Pinku - 5 years, 1 month ago
Puneet Pinku
May 16, 2016

3 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...