Proving a palindromic integer with an even number of digits is divisible by 11

Question

I'm in an introductory course for discrete math so I'm a novice at English proofs. I'm not sure if my reasoning here is valid or if I'm using modular arithmetic correctly. Specifically the line I marked with $(**)$. I would appreciate any feedback. Sorry if any part of the proof seems obvious we are generally expected to spell everything out.

---

Objective: Prove every palindromic integer with an even number of digits is divisible by $11$.

Proof:

Consider a palindromic integer $p$ in the form of $x_{1} x_{2} …. x_{n-1}x_{n}x_{n}x_{n-1}...x_{2}x_{1}$ where $p$ has $2n$ digits. This can be expanded as:

$$x_{1} + x_{2}\cdot10 + … + x_{n}\cdot10^{n} + x_{n}\cdot10^{n+1} + … + x_{2}\cdot10^{2n} + x_{1}\cdot10^{2n+1}$$

$(**)$ $10 \equiv -1 \pmod{11}$ so if we take $\pmod{11}$ of the expression we can replace $10\equiv -1$.

$$x_{1} + x_{2}\cdot(-1) + … + x_{n}\cdot(-1)^{n} + x_{n}\cdot(-1)^{n+1} + … + x_{2}\cdot(-1)_{2n} + x_{1}\cdot(-1)^{2n+1}$$

Since we know $2n$ is even (and therefore $2n + 1$ is odd), and $(-1)^{a} = 1$ when $a$ is even and $= -1$ when $a$ is odd we can rewrite the expression as:

$$x_{1} - x_{2} + … + x_{n} - x_{n} + … + x_{2} - x_{1} = 0$$

Therefore since $p \equiv 0 \pmod{11}$, we have that $11$ divides $p$.

Answer 1

You have some off-by-one errors, but you have the right idea. Note that: \begin{align*} p &= (x_1 + x_2 10 + \cdots + x_n 10^{n-1}) + (x_{n} 10^n + x_{n-1} 10^{n+1} + \cdots + x_1 10^{2n - 1}) \\ &= \sum_{k=1}^n x_k 10^{k-1} + \sum_{k=1}^n x_k 10^{2n-k} \\ &= \sum_{k=1}^n x_k10^{k-1}(1 + 10^{2n - 2k - 1}) \\ &\equiv \sum_{k=1}^n x_k10^{k-1}(1 + (-1)^{2n - 2k - 1}) \pmod {11} \qquad\qquad\text{since $10 \equiv -1 \pmod{11}$} \\ &\equiv \sum_{k=1}^n x_k10^{k-1}(1 -1) \pmod {11} ~~~~~~~~~~~~~~~~~~~\qquad\qquad\text{since $2n - 2k - 1$ is odd} \\ &\equiv 0 \pmod {11} \end{align*}

Answer 2

of course a proof is a proof, and questions of proof style are to some extent a matter of personal taste. but when you have a valid proof idea, there is often something to be learned by looking to see if the exposition can be improved on, or, even if no improvement seems possible, insight may still be increased by finding an alternative route to the same goal. good clues may often be found by focusing on any part of the argument which requires more mental effort.

sometimes the most complex idea involved may be dealt with in one or two "harder" lemmas, from which, once proved, everything follows fairly easily. for example:

LEMMA 1 for positive integers $k,n$ with $k \le 2n$ $$ 10^{k-1} + 10^{2n-k} \equiv_{11} 0 $$ PROOF since $10 \equiv_{11} -1$ we have $$ 10^{k-1} + 10^{2n-k} \equiv_{11} (-1)^{k-1}+(-1)^{2n-k} \equiv_{11} (-1)^{k-1}+(-1)^{-k} = 0 $$ LEMMA 2 any palindromic integer $M$ with an even number $(2n)$ of digits may be written as $$ M = \sum_{k=1}^n (10^{k-1} + 10^{2n-k})d_k $$ where the $d_k$ are integers $0 \le d_k \le 9$

Answer 3

I think that it is worth mentioning the (first) divisibility by 11 rule given at https://en.wikipedia.org/wiki/Divisibility_rule.

Since you are given that $n$ is palindromic with an even # of digits, it is immediate that the sequence of numbers in the odd positions is a reversal of the sequence of numbers in the even positions. Given wikipedia's rule, this (also) makes the conclusion immediate.

Of course, this begs the question whether the problem allows the assumption that the wikipedia rule is accurate, or whether this rule needs to (first) be proven.