How to compute $\gcd(d^{\large 671}\! +\! 1, d^{\large 610}\! −\!1),\ d = \gcd(51^{\large 610}\! +\! 1, 51^{\large 671}\! −\!1)$

Question

Let $(a,b)$ denote the greatest common divisor of $a$ and $b$.

With $ \ d = (51^{\large 610}\! + 1,\, 51^{\large 671}\! −1)$

and $\ \ x \,=\, (d^{\large 671} + 1,\, \ d^{\large 610} −1 )$

find $\ X = (x\bmod 10)$

I used $y=51^{61}$ to reduce $d$ to $d=(y^{10}+1,y^{11}-1) = (y^{10}+1,y+1)$.

What should I do now?

Answer 1

As in the proofs here and here, we reduce to coprime powers then apply the $\rm\color{#90f}{Euclidean}$ algorithm.

$a = 51^{\large 61}\Rightarrow\, d = (a^{\large 11}-1,\,a^{\large 10}+1) = (a\!+\!1,2) = 2\,$ by $\,\bf T1\,$ below, with $\ s = -1$

$a\, =\, d^{\large 61}\Rightarrow\,x = (a^{\large 11}+1,\,a^{\large 10}-1) =\, a\!+\!1 = d^{\large 61}\!+1 = 2^{\large 61}\!+1\,$ by $\,\bf T1,\,$ $\,s = 1$

${\bf T1}\,\ (s,a)\! =\!1\, \Rightarrow\, (a^{\large 11}\!+s,\,a^{\large 10}-s)\, = (a\!+\!1,\,1\!-\!s).\ $ Proof: $\,\rm\color{#90f}{using}$ $\ (x,y) = (x,\, y\bmod x)$

$\begin{align} (\color{#0a0}{a^{\large 11}}\!+s,\,{a^{\large 10}}\!-s) &= (\color{#0a0}{s}(\color{#0a0} a\!+\!1),\, {a^{\large 10}}\!-s)\ \ \ \,{\rm by}\ \ \bmod a^{\large 10}\!-s\!:\,\ a^{\large 10}\!\equiv s\,\Rightarrow\, \color{#0a0}{a^{\large 11}}\!\equiv a^{\large 10}a \equiv \color{#0a0}{sa} \\[.2em] &= \ \ \ \, (a\!+\!1,\ \,\color{#c00}{a^{\large 10}}\!-s)\ \ \ \ {\rm by}\,\ \ (s,\,a^{\large 10}\!-s) = (s,a^{\large 10})=1, \ \, {\rm by}\,\ \ (s,a) = 1\\[.2em] &=\ \ \ \ (a\!+\!1,\ \ \ \color{#c00}1\, -\, s) \ \ \ \ {\rm by}\ \ \bmod a+1\!:\ \ \ \ a\equiv -1\,\Rightarrow\, \color{#c00}{a^{10}}\equiv (-1)^{10}\equiv\color{#c00} 1 \\[.2em] \end{align}$

Answer 2

$$51^{671}=51^{610}\times 51^{61}-1=(51^{610}+1)51^{61}-(51^{61}+1)$$

$$(51^{61}, 51^{61}+1)=1$$

So we may write:

$$d=(51^{610}+1, 51^{671}-1)=(51^{610}+1, 51^{61}+1)$$

$$51^{61}+1=52 k=2\times 26 k$$

$$51^{610}+1=52 k_1 +2=2(26 k_1+1)$$

$$(26, 26k_1+1)=1$$

However $k$ and $26 k_1+1$ may have common divisors. If we assume $d=2$ then we have:

$$x=(2^{671}+1, 2^{610}-1) $$

$$2^{671}+1=(2^{610}-1)2^{61} +2^{61}+1$$

$(2^{61},2^{61}+1)=1$, Therefore:

$$x= 2^{61}+1$$

Answer 3

First note: $\gcd(a^m \pm 1, a+1)=\gcd((a^{m}\pm 1)-(a^{m}+a^{m-1}),a+1) = \gcd(a^{m-1}\mp 1, a+1)$

And via induction $\gcd(a^{m}+1, a+1) = \gcd(2, a+1)$ if $m$ is even. $\gcd(a^{m} - 1,a+1) =\gcd(0, a+1) = a+1$ if $m$ is even. (And the opposite results if $m$ is odd).

so if we let $a= 51^{61}$.

Then $\gcd(51^{610} + 1, 51^{671} - 1)=$

$\gcd(a^{11}-1,a^{10} + 1)=$

$\gcd((a^{11} -1)-(a^{11} + a), a^{10} + 1) =$

$\gcd(a^{10} + 1, a+ 1) = 2$

...

Let $b = 2^{61}$ and so

$\gcd(2^{671}+1, 2^{610} -1)= \gcd (b^{11} + 1, b^{10} -1)=$

$\gcd((b^{11}+1)-(b^{11}-b), b^{10}-1)=\gcd(b^{10}-1,b+1)=b+1= 2^{61}+1$