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$.

  • $\begingroup$ I think $(ab - cd)$ should be $(\overline{ab} - \overline{cd})$. $\endgroup$
    – soupless
    May 9 at 15:25
  • $\begingroup$ $1300-13$ Is indeed divisible by $99.$ But neither $1300$ nor $13$ is divisible by $99.$ $\endgroup$ May 9 at 15:28
  • $\begingroup$ I suppose $\gcd(9999,9999)=9999$ is not allowed, but what is allowed? Can we have $a=c$ but $b≠d$? $\endgroup$
    – MJD
    May 9 at 15:31
  • $\begingroup$ The simple fact that $x-y=uv$ certainly doesn't imply that $u$ divides $x$ and $y$! Just think about that for a bit. $\endgroup$
    – TonyK
    May 9 at 15:33
  • $\begingroup$ 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$. $\endgroup$
    – fleablood
    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)=$


$\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, 99) \gcd(80\times 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) $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.