WordGPT

gcd(2¹⁰⁰ βˆ’ 1, 2⁢⁰ βˆ’ 1)

Exercise Β· Level 4 (Hard)

Find the greatest common divisor of 21002^{100} βˆ’ 1 and 2602^{60} βˆ’ 1.

gcd⁑(2100βˆ’1,Β 260βˆ’1)\gcd\left(2^{100}-1,\ 2^{60}-1\right)

wordgptpro.com

Solution

  1. For a>ba>b write 2aβˆ’1=2aβˆ’b(2bβˆ’1)+(2aβˆ’bβˆ’1)2^a-1=2^{a-b}(2^b-1)+(2^{a-b}-1). A common divisor of the first two numbers on the right divides the sum, so

    gcd⁑(2aβˆ’1, 2bβˆ’1)=gcd⁑(2bβˆ’1, 2aβˆ’bβˆ’1)\gcd(2^a-1,\,2^b-1)=\gcd(2^b-1,\,2^{a-b}-1)
    (1)
  2. The exponents change exactly as in Euclid's algorithm, so repeating this step ends at the gcd of the exponents:

    gcd⁑(2aβˆ’1, 2bβˆ’1)=2gcd⁑(a,b)βˆ’1\gcd(2^a-1,\,2^b-1)=2^{\gcd(a,b)}-1
    (2)
  3. Here gcd⁑(100,60)=20\gcd(100,60)=20, so

    gcd⁑(2100βˆ’1, 260βˆ’1)=220βˆ’1=1 048 575\begin{aligned}&\gcd\left(2^{100}-1,\,2^{60}-1\right)\\&=2^{20}-1\\&=1\,048\,575\end{aligned}
    (3)
Answer220βˆ’1=10485752^{20}-1=1048575

wordgptpro.com

Need a hint?

Run Euclid's algorithm on the exponents: 2a2^{a} βˆ’ 1 and 2b2^{b} βˆ’ 1 behave like a and b.

gcd(21002^{100} βˆ’ 1, 2602^{60} βˆ’ 1) = 2202^{20} βˆ’ 1 = 1,048,575.

How to work it out

  1. For a>ba>b write 2aβˆ’1=2aβˆ’b(2bβˆ’1)+(2aβˆ’bβˆ’1)2^a-1=2^{a-b}(2^b-1)+(2^{a-b}-1). A common divisor of the first two numbers on the right divides the sum, so

    gcd⁑(2aβˆ’1, 2bβˆ’1)=gcd⁑(2bβˆ’1, 2aβˆ’bβˆ’1)\gcd(2^a-1,\,2^b-1)=\gcd(2^b-1,\,2^{a-b}-1)
    (1)
  2. The exponents change exactly as in Euclid's algorithm, so repeating this step ends at the gcd of the exponents:

    gcd⁑(2aβˆ’1, 2bβˆ’1)=2gcd⁑(a,b)βˆ’1\gcd(2^a-1,\,2^b-1)=2^{\gcd(a,b)}-1
    (2)
  3. Here gcd⁑(100,60)=20\gcd(100,60)=20, so

    gcd⁑(2100βˆ’1, 260βˆ’1)=220βˆ’1=1 048 575\begin{aligned}&\gcd\left(2^{100}-1,\,2^{60}-1\right)\\&=2^{20}-1\\&=1\,048\,575\end{aligned}
    (3)
LaTeX source of the formulas on this page
\[ 2^{20}-1=1048575 \]
\[ \gcd(2^a-1,\,2^b-1)=\gcd(2^b-1,\,2^{a-b}-1) \]
\[ \gcd(2^a-1,\,2^b-1)=2^{\gcd(a,b)}-1 \]
\[ \gcd\left(2^{100}-1,\,2^{60}-1\right)=2^{20}-1=1\,048\,575 \]

Questions

What is the answer to: gcd(2¹⁰⁰ βˆ’ 1, 2⁢⁰ βˆ’ 1)?

gcd(21002^{100} βˆ’ 1, 2602^{60} βˆ’ 1) = 2202^{20} βˆ’ 1 = 1,048,575.

What is the key idea?

The gcd of 2a2^{a} βˆ’ 1 and 2b2^{b} βˆ’ 1 is 2^gcd(a,b) βˆ’ 1.

Is there a hint?

Run Euclid's algorithm on the exponents: 2a2^{a} βˆ’ 1 and 2b2^{b} βˆ’ 1 behave like a and b.

Related problems

More number theory problems

    gcd(2¹⁰⁰ βˆ’ 1, 2⁢⁰ βˆ’ 1): answer and solution | WordGPT