Proving that a non-trivial GCD of strings $a$ and $b$ exists iff $a+b=b+a$

Question

Firstly, assume there are two strings $a$ and $b$. Let the GCD of the two strings is the longest string which divides both. String $t$ divides $s$ iff $s = t + t + \dots + t$.

How can I show that a non-trivial GCD exists iff $a + b = b + a$?

One proof I have seen is that: $n \cdot len(gcd) + m \cdot len(gcd) = m \cdot len(gcd) + n \cdot len(gcd)$, but this seems very incomplete.

Answer 1

Assume we are given two non trivial strings $a,b$ such that

$$ a+b=b+a$$

let $len(a) = m$ and $len(b) = n$. W.l.o.g. let $n\geq m$. Then

\begin{align} a_1&=b_1 \\ a_2&=b_2\\ &.\\&.\\&.\\ a_m&=b_m \end{align}

Simply by comparing the strings $a+b$ and $b+a$. So $a$ is a substring of $b$, and specifically,

$$b= a+t$$

So we get

\begin{align} a+a+t&=t+ a+a \\ \end{align}

Where $t$ has length $n-m$

If $n-m>2m$ then $t=2a+q$, so

\begin{align} 4a + q &= 2a + q + 2a\\ \implies 2a + q &= q + 2a\\ \end{align}

Where the total length of the strings on either side of the last equality is $n-m<n+m$.

On the other hand, if $n-m<2m$

Then $2a = t + q$, so we get

\begin{align} t+q+t &= t+t+q \\ \implies q+t &= t+q \\ \end{align}

But still, the total length of the strings on either side is now $2m<n+m$

So notice that given an equality of strings length $m+n$ we can induce a new equality where the strings on either side have a total length of strictly less than $n+m$, if $n\neq m$, by writing the longer string as the shorter one plus some factor. We can keep doing this, shortening the total length of the strings we are comparing, until we reach an expression which cannot be shortened, which is only possible if both strings on either side of the equality have the same length, but that just means they are equal, and so their $gcd$ is just themselves. You can then work your way up again, adding this $gcd$ to itself to get back the original equality, which then necessarily also has some nom trivial divisor, which implies that it has a $gcd$

Answer 2

One direction of the equivalence is easy. If $a,b$ have a non-trivial gcd $c$, then $a$ is the sum of $m$ copies of $c$, which I'll write $a=m*c$, and $b=n*c$. Then clearly $a+b$ and $b+a$ are both equal to $(m+n)*c$.

The other direction is more tricky, so I'll start by putting it in a form that's easier to work with. First, it suffices to show that $a,b$ have a non-trivial common divisor; if there exists one, then the gcd must exist and be non-trivial too. Moreover, I'll assume both strings are non-empty; indeed, without this assumption, the implication is false. Finally, by symmetry, we'll assume that $len(a) \leq len(b)$. In short, I'll show the following statement.

For any $n \geq 1$, for any strings $a,b$ with $0<len(a) \leq len(b)=n$, if $a+b=b+a$, then $a,b$ have a non-trivial common divisor.

You should check that this statement implies the one you want. As the form of the statement may suggest, we will prove it by strong induction on $n$, the length of $b$.

Strong induction doesn't need a base case, so we skip straight to the inductive step. Fix a length $n$, and suppose that for all non-empty strings $a',b'$ of length (strictly) smaller than $n$, if $a'+b'=b'+a'$, then $a',b'$ have a non-trivial common divisor.

Now, suppose that $a+b=b+a$, where $b$ has length $n$ (and $0<len(a) \leq n$). Because $a+b=b+a$, we see that $a$ is a leading substring of $b+a$. Since $len(a) \leq len(b)$, this further tells us that $a$ is a leading substring of $b$; that is, $b=a+c$ for some $c$. Thus our equality becomes $$ a+a+c = a+c+a. $$ We can cancel the leading $a$ from this equality and get $a+c=c+a$. We now have two cases: if $c$ is empty, then $a=b$ and we're done. Otherwise, $a,c$ are non-empty strings, and they have length less than $n$ because they sum to $b$ (which has length $n$). The induction hypothesis lets us conclude from $a+c=c+a$ that $a,c$ have a non-trivial common divisor $d$. Hence $$ a=m*d, \qquad c=n*d, $$ and so $b=(m+n)*d$. Thus $d$ is a non-trivial common divisor of $a,b$, and this is what we wanted to show.

Answer 3

If a non-trivial GCD $g$ exists, then $a+b$ and $b+a$ are the same number of copies of $g$.

In the other direction, if $a+b = b+a$, then one (say $b$) must equal the leading substring of the other, so that $a = b + c$ for some string $c$. We may delete the leading $b$ string from each side of the equality $a+b = b+a$ (this system of strings is a cancellative monoid) to obtain $c+b = b+c$.

When we continue this process we may track the lengths of the strings $a$, $b$, $c$, etc., that arise. These lengths are the iterates of the Euclidean algorithm (the slow version, in which we subtract instead of computing remainders). We know this algorithm halts. So the gcd of $a$ and $b$ is the last string of positive length before it halts.