On the GCD of two palindromes.

Question

I had an observation. Which I will discuss below. My question will be Is my observation correct? If so, how can one prove it?

Observation:

Consider the string of palindromes below:

$100...01$ and $111...11$

I observed that:

$gcd(100...01,111...11)=1$ if the length of the string is odd while

$gcd(100...01,111...11)=11$ if the length of the string is even.

Thank you so much for the big help.

Answer 1

What I'm about to do below is called the Euclidean algorithm. If you're not familiar with it, I can show you some explanations of it on other questions/Web sites if you ask me in the comments.

We have: $$\text{gcd}\left(10^k+1, \sum_{i=0}^k 10^k\right)$$ The second element is bigger, so subtract it by the first element: $$\text{gcd}\left(10^k+1, \sum_{i=1}^{k-1} 10^k\right)$$ Notice how the second element now has no ones place or $10^k$ place. Now, the first element is bigger, so subtract it by the second element, which affects all of the digits of the first element except the first and the last: $$\text{gcd}\left(91+\sum_{i=2}^{k-1} 8\cdot 10^k, \sum_{i=1}^{k-1} 10^k\right)$$ Notice how I changed the summation index from $i=1$ to $i=2$ and brought the tens place out into to make $91$ in front. Now, do this $8$ more times, getting rid of the summation and subtracting $91$ by $80$ which gives us $11$: $$\text{gcd}\left(11, \sum_{i=1}^{k-1} 10^k\right)$$

Now, $11$ is prime so the GCD is either $1$ or $11$:

• If $k$ is even, then we have an odd number of $1$s in the second element and it is not divisible by $11$, so the GCD is $1$.
• If $k$ is odd, then we have an even number of $1$s in the second element and it is divisible by $11$, so the GCD is $11$.

Thus, since I just proved a restatement of your observation, your observation was indeed correct. Good job!