# Math Help - Palindromes

1. ## Palindromes

I have got a question to palindromes like 43934 or 99300399 (u can read them from both sides)... my teacher wants us to show that EVERY numer which cannot be devided through 10 has a multiple which is a palindrome...how can i attest that?! i have thought of it for hours but i have no idea how i could attest it...do you have any ideas?

2. This is an excellent problem, and I found it very difficult. Here is an attempt at a solution.

Suppose first that n is an odd number that is not a multiple of 5. Then n is co-prime to 10, so by Euler's totient theorem $10^{\phi(n)}\equiv1\!\!\!\pmod{n}$. If $N = 1 + 10^{\phi(n)} + 10^{2\phi(n)} + \ldots + 10^{(n-1)\phi(n)}$ then $N\equiv0\!\!\!\pmod{n}$. Thus N is a palindromic number that is a multiple of n.

Even for small values of n, this produces a huge number. For example, if n=21 then N is a number with 241 digits, consisting of 21 1s, each separated by 11 0s. Compare that with the smallest palindromic multiple of 21, which is 252.

Things get harder when n is divisible by a power of 2 or 5. Here's a sketch of how to handle powers of 2. Powers of 5 would be handled by a similar procedure. Of course, n cannot be a multiple of both 2 and 5 because we are told that it is not a multiple of 10.

So suppose that $n=2^km$, where m is odd (and not a multiple of 5). Let $l$ be the number of digits in $2^k$, and suppose for convenience that $l\leqslant\phi(m)$. Let p denote the number obtained from $2^k$ by reversing the order of its digits, and let $X = 10^{(m+1)\phi(m)-l+1}p+2^k$.

It may be helpful to have an example at hand. Suppose that $n=48 = 2^4\times3$. Then k=4, $2^k=16$, $l=2$ and $p=61$ (=16 with the digits reversed). Also, $m=3,\ \phi(3)=2$, and $(m+1)\phi(m)-l +1 = 7$. So for this example, X is the number $61\times10^7+16 = 610000016$. This is palindromic, and it is a multiple of 16. But it is not a multiple of 3.

The idea of the rest of the proof is to add numbers of the form $10^{r\phi(m)}$ (each of which is congruent to 1 mod m) to X so as to make it a multiple of m.

In the case of the example, that has the effect of replacing 0s by 1s in some or all of the asterisked places in the number 61*0*0*16. In this case, the number 610000016 is congruent to 2 (mod 3). So we only need to replace one of the asterisks by a 1, leaving the others as 0s. In order to keep the number palindromic, we replace the middle asterisk by 1, finally getting the number 610010016 as a palindromic multiple of 48. (As with the previous example, there are much smaller palindromic multiples of 48, such as 8448.)

Having dealt with that example I don't have the stamina to try to write out the general proof. I hope that the idea of the procedure is clear.

I cut corners at one point by assuming that $l\leqslant\phi(m)$. If that is not the case then you simply replace $\phi(m)$ by a multiple of $\phi(m)$ that is greater than $l$.

It's a shame that the case where n has factors of 2 or 5 is so messy. I hope someone can come up with a neater argument.

3. Hi,

the same problem was recently asked on another forum, and some answers were provided.

In the case when $\gcd(n,10)=1$, a smaller solution can be given: since Euler' theorem gives $10^{\phi(n)}\equiv1\!\!\!\pmod{n}$, the number $10^{\phi(n)}-1$ is a multiple of $n$, and it already is a palindrome: it has only 9's in it.

Opalg's solution may however give an answer for the general case, along with an idea from the other forum; maybe it even lies entirely in the other forum but not clearly explained. Here's the way to procede:

Let us write $n=2^k 5^l m$ with $\gcd(m,10)=1$, and either $k=0$ or $l=0$.

- Let $u=2^k 5^l$, and $T$ be the following palindromic number ending by $u$: $T=10^{k+l+1} v + u$, if $v$ is the base 10 "mirror" of $u$. Note that $u$ divides $T$ (because $u|10^{k+l+1}$).

- For $m$, remember
$10^{\phi(m)}\equiv1\!\!\!\pmod{m}$ so that, for any $r\geq 1$, we have $M=1+10^{r\phi(m)}+10^{2r\phi(m)}+\cdots+10^{(m-1)r\phi(m)}\equiv m\equiv 0\!\!\!\pmod{m}$, i.e. $M$ is a (palindromic) multiple of $m$.

- Here's the "coup de grace": choose $r$ such that $r\phi(m)$ is larger than the number of digits of $T$, and let $N=MT$. By the above, $N$ is a multiple of $n$, and $N$ is a palindrome: it looks like $T0\cdots0T0\cdots0T$ with $m$ times " $T$" and zeros in-between.

This provides a pretty huge palindromic multiple, but in a somewhat neat way...

4. ## i am confused :D

Well, thank you first at all^^
but somehow i dont understand this...it contains so many variables like u,m,n,k,l,N,T and now i am more than confused
could somebody explain it in easy language or just explain the variables?
and by the way what is 10^phi(m)? =) i thought it was the funktion which donates to every m the quantity of numbers throught which m cannot be devided.
so for m = 7 (phi(m)=6 (1,2,3,4,5,6) it would mean: 10^6 = 1 (mod n)
doesn't a mod n give u back the rest-number which results from a devided through n??
so 1 (mod n) = n always...? hum..??

and in this example it would mean: 10^6 = 7^^
something is wrong here can u explain it to me?
thx =)

5. Originally Posted by Jamie90
Well, thank you first at all^^
but somehow i dont understand this...it contains so many variables like u,m,n,k,l,N,T and now i am more than confused
could somebody explain it in easy language or just explain the variables?
and by the way what is 10^phi(m)? =) i thought it was the funktion which donates to every m the quantity of numbers throught which m cannot be devided.
so for m = 7 (phi(m)=6 (1,2,3,4,5,6) it would mean: 10^6 = 1 (mod n)
doesn't a mod n give u back the rest-number which results from a devided through n??
so 1 (mod n) = n always...? hum..??

and in this example it would mean: 10^6 = 7^^
something is wrong here can u explain it to me?
thx =)
... like Opalg said, this is a difficult problem, and I doubt you were expected to completely solve it if you don't have some knowledge of number theory, like modular arithmetic (properties of the "modulo"), or Euler's theorem. I shall answer your questions about definitions, but I won't be able to give you a thorough explanation of the previous post, it would require many steps to bring you to what you would need, and most of all you're certainly not expected to learn that by yourself, or to have it taught to you.

$a\!\!\!\pmod n$ can indeed be understood as the remainder when $a$ is divided by $n$. If you divide $n$ by $n$, the quotient is 1 and the remainder is 0, so that $n\equiv 0\!\!\!\pmod n$. And you don't have $1\equiv 0\!\!\!\pmod n$, except if $n=1$.

The only theorem we used is Euler's theorem, which says that if $a$ and $n$ are coprime, then $a^{\phi(n)}\equiv 1\!\!\!\pmod n$ or, in other words, $n$ divides $a^{\phi(n)}-1$. For instance, if $n$ and 10 are coprime, then we get that $n$ divides $10^{\phi(n)}-1$. Since $10^{\phi(n)}-1=999\cdots999$ (with $\phi(n)$ times "9") is obviously a palindrom, this gives the answer to your problem in this case (i.e. if $n$ and 10 are coprime).

The other case is a refinement of this one, and you could first spend time studying Euler's theorem, like look for proofs in books for instance, I don't know. Or maybe you can look at examples: using a calculator or a computer program, look for palindromic multiples of small numbers, perhaps find a pattern and derive a proof by yourself for some cases... Depending on your knowledge, I don't know what the teacher expected from you, but obviously not to draw Euler's theorem from a magic hat .