Proof that for any $x$ there is a $y$ such that $xy$ is a palindrome

Question

I'm wondering how I would prove

For any $x$ there exists at least one $y$ such that $xy$ is a palindrome.

For example: $91\cdot 99=9009$.

Answer 1

Depending whether you allow leading zeroes (i.e. whether you allow $010$ as a palindrome representation of ten and similar ones), answer is either yes or no.

If you don't allow such leading zeroes, there are easy counterexamples (I'm leaving them for you to find).

If you do allow them, then the statement is true. It's enough to prove the following:

For any integer $n>0$ there is a positive multiple of $n$ such that it's decimal expansion has the form $11...100...0$.

(hint to the proof of this: consider numbers $1,11,111,1111,...$ and look at reminders when dividing by $n$. Some two of these will give the same reminder)

Answer 2

As Marcus Andrews correctly points out, if leading zeros are disallowed, then trailing zeros are also disallowed, and a palindromic multiple of any $x \ge 1$ with trailing zeros would be impossible.

However this can be addressed (for any radix base $b \ge 2$) either by allowing leading zeros to be used, or by restricting $x$ to be coprime to base $b$.

Suppose first that $x$ is coprime to $b$, so that by Euler's generalization of Fermat's Little Theorem:

$$ b^{\varphi(x)} \equiv 1 \bmod{x} $$

where Euler's function $\varphi(x)$ counts the coprime residues mod $x$.

Then $\sum_{k=1}^x b^{(k-1)\varphi(x)}$ is divisible by $x$ (since each of the $x$ summands is congruent to $1 \bmod{x}$) and palindromic when written out in base $b$.

Further, in the case $x$ is not coprime to $b$, if we are allowed to prepend $n$ leading zeros to such an expression as well as $n$ trailing zeros, these may be used to provide a multiple of any factor of $x$ which divides a corresponding power $b^n$.

We have shown that each $x \ge 1$ has a multiple that is expressible in base $b$ (possibly with leading zeros) by a palindrome consisting solely of zeros and ones.

Added: @Akiva Weinberger has proposed that leading zeros can be avoided in all cases where $x$ is not a multiple of base $b$. We show that this is correct.

Let $x=uv$ be factored so that $u$ is the largest divisor of $x$ coprime to $b$, and hence $v$ contains only those prime factors of $x$ that are common to $b$.

If $b$ does not divide $x$, then $b$ does not $v$. However $v$ divides some sufficiently large power $b^n$, while the base $b$ representation of $v$ does not have a trailing zero. Let $w$ be the result of reversing the base $b$ representation of $v$, and thus $wb^n + v$ is a multiple of $v$ whose base $b$ representation is a palindrome.

Modify the construction $\sum_{k=1}^u b^{M\cdot (k-1)\varphi(u)}$ for a base $b$ palindrome divisible by $u$, to include an integer parameter $M \ge 1$. Choose $M$ sufficiently large that $b^{M\cdot \varphi(u)} \gt wb^n + v$.

Then the spacing between 1's in the base $b$ representation of $\sum_{k=1}^u b^{M\cdot (k-1)\varphi(u)}$ is sufficiently wide that:

$$ \left( \sum_{k=1}^u b^{M\cdot (k-1)\varphi(u)} \right) (wb^n + v) $$

is a palindrome, has no trailing zero, and is divisible by $x=uv$.