find great common divisor of $\overline{abcd}$ and $\overline{cdab}$

For integer numbers $$\overline{abcd}$$ and $$\overline{cdab}$$ find great common divisor of $$\overline{abcd}$$ and $$\overline{cdab}$$

I tried $$\overline{abcd} = 100\overline{ab}+\overline{cd} \\ \overline{cdab} =100\overline{cd} +\overline{ab}\\ \Longrightarrow \overline{abcd}-\overline{cdab}=99(\overline{ab}-\overline{cd}).$$

I think $$\gcd(abcd,cdab)=99$$.

But then I find $$\gcd(9680, 8096)=176$$.

• I think $(ab - cd)$ should be $(\overline{ab} - \overline{cd})$. May 9 at 15:25
• $1300-13$ Is indeed divisible by $99.$ But neither $1300$ nor $13$ is divisible by $99.$ May 9 at 15:28
• I suppose $\gcd(9999,9999)=9999$ is not allowed, but what is allowed? Can we have $a=c$ but $b≠d$?
– MJD
May 9 at 15:31
• The simple fact that $x-y=uv$ certainly doesn't imply that $u$ divides $x$ and $y$! Just think about that for a bit. May 9 at 15:33
• The conclusion you should reach from $abcd -cdab = 99(ab-cd)$ is that $\gcd(abcd,cdab) = \gcd(abcd, [99(ab - cd)])= \gcd(abcd, 99)\gcd(abcd,ab-cd)$. It seems implied, but not stated, the $ab,cd$ are relatively prime so $\gcd(abcd,ab-cd)$ is implied to be $1$ (Although it need not be). But the $99$.... it is does not need to have any factors in common with $abcd$ or with $cdab$. May 9 at 15:56

It is indeed true that the $$abcd-cdab = 99(ab-cd)$$.

ANd that does indeed mean that the $$\gcd(abcd,cdab)$$ does divide $$99(ab-cd)$$,

But that in no way means that $$99$$ divides or is or has any factors in common with $$\gcd(abcd,cdab)$$. (It doesn't mean it doesnt but it doesn't mean it does).

Indeed $$9680 - 8096 = 99\cdot (96-80)$$. And that means that all the factors $$9680$$ and $$8096$$ have in common are also factors of $$99\cdot(96-80)$$. But it doesn't mean that all of those factors are factors of $$99$$-- some of the factors might be factors of $$96-80$$. Nor does it mean that all the factors (or indeed any of the factors) of $$99$$ are common factors are $$9680$$ and $$8096$$.

What is does mean is that some distributed between the $$99$$ and the $$96-80$$ all the factors in common, and the $$\gcd$$ are to be found and indeed. $$11|99$$ and $$16 = 96-80$$ and the $$\gcd(9680,8096) = 176 = 11\cdot 16$$.

The conclusion you should reach is:

$$\gcd(abcd,cdab) = \gcd(abcd, abcd-cdab)=$$

$$\gcd (abcd, 99(ab-cd))=$$

$$\gcd(99,abcd)\cdot \gcd(abcd, ab-cd)=$$

etc.

$$\gcd(9680-8096) = \gcd(9680,9680-8096)=$$

$$\gcd(9680, 99\cdot 16) =$$

$$\gcd(9680, 99) \gcd(9680, 16)=$$

$$\gcd(9680- 96\cdot 99, 99)\gcd(9680-1600, 16)=$$

$$\gcd(176,99)\gcd(8080,16)=$$

$$\gcd(176-99, 99) \gcd(80\times 101, 16) =$$

$$\gcd(77,99)\gcd(80,16)\gcd(101,16)=$$

$$\gcd(77, 99-77)\gcd(5\times 16, 16)\gcd(101-6*16,16)=$$

$$\gcd(77,22)\cdot 16\cdot(5,16) =$$

$$\gcd(77-3\cdot 22, 22)\cdot 16\cdot \gcd(16-3\cdot 5, 5)=$$

$$\gcd(11,22)\cdot 16\cdot \gcd(1,5) =$$

$$\gcd(11, 2*11)\cdot 16 \cdot 1=$$

$$11 \cdot 16 \cdot 1 = 176$$.

We'll assume $$\overline{ab} \ne \overline{cd}$$, since the solution is obvious in that case.

Let $$n = \overline{ab}/GCD(\overline{ab}, \overline{cd})$$, $$m = \overline{cd}/GCD(\overline{ab}, \overline{cd})$$, and $$g = GCD(100m + n,100n +m)$$. Clearly $$m$$ and $$n$$ are relatively prime and $$GCD(\overline{abcd}, \overline{cdab}) = GCD(\overline{ab}, \overline{cd})g$$. We also have that $$g = GCD(100m + n,99(n-m)) = GCD(100m+n, 101(m+n))$$, so $$g | 99(n-m)$$ and $$g | 101(n+m)$$. We can't possibly have $$g | 101$$, and $$101$$ is prime, so $$g | m + n$$. That means that $$g$$ and $$n - m$$ are relatively prime, since $$m$$ and $$n$$ are relatively prime, and so $$g | 99$$. Further, any number that divides both $$99$$ and $$m+n$$ also divides $$g$$, since it would divide both $$99(n-m)$$ and $$99m + m + n$$. So $$g = GCD(m + n, 99)$$.

Thus, we have $$GCD(\overline{abcd}, \overline{cdab}) = GCD(\overline{ab}, \overline{cd})GCD\left(\frac{\overline{ab} + \overline{cd}}{GCD(\overline{ab}, \overline{cd})}, 99\right),$$ or equivalently, $$GCD(\overline{abcd}, \overline{cdab}) = GCD\left(\overline{ab} + \overline{cd}, 99\cdot GCD(\overline{ab}, \overline{cd})\right)$$