# Solutions to $x_1+2x_2+3x_3+4x_4+5x_5+6x_6+7x_7+8x_8+9x_9+10x_{10}\equiv0\mod11$

How many solutions does the following equation have:

$x_1+2x_2+3x_3+4x_4+5x_5+6x_6+7x_7+8x_8+9x_9+10x_{10}\equiv0\mod11$

where

$x_{1...9} \in \{0,1,2,3,4\ ...\ 8,9\}$ and $x_{10}\in\{0,1,2,3,4\ ...\ 9,10\}$?

I've being trying to solve the equation with generating functions. The closed form that I've arrived at is:

$(1-x^{10})(1-x^{20})(1-x^{30})...(1-x^{110}) \above 1pt (1-x)(1-x^2)(1-x^3)...(1-x^{10})$

where the sum of coefficients of all the terms of the form $x^n$ where $n\equiv0\mod11$, is the answer to the original problem. But it seems to make it even harder.

Can somebody help me with the solution or just give a hint of what else I might try? I swear I've spent with the problem quite a while now, so I think I simply need someone to have a fresh look on it.

Rewrite it as $$10x_{10} \equiv -x_1 - \ldots - 9x_9 ~\text{mod}~ 11.$$ Since $10 \in (\mathbb{Z}/11\mathbb{Z})^*$, this equation has exactly one solution for each choice of $x_1,\ldots,x_9$, namely $x_{10} := x_1 + \ldots + 9x_9 ~ \text{mod}~ 11$. So in total there are $10^9$ solutions.

Edit: Clarification.

$10 \in (\mathbb{Z}/11\mathbb{Z})^*$ means that $10$ is invertible in the ring $\mathbb{Z}/11\mathbb{Z}$. You may think of that ring as "integers modulo 11". Note that $10 \equiv -1 ~\text{mod}~ 11$ and thus $10 \cdot 10 \equiv 1 ~\text{mod}~ 11$. As we see, $10$ is its own inverse in $\mathbb{Z}/11\mathbb{Z}$. Multiplying both sides of the rewritten equation by $10$ yields $$10\cdot10x_{10} \equiv 10\cdot( -x_1-\ldots-9x_9)~\text{mod}~11 ~~~\Leftrightarrow~~~ x_{10} \equiv (-1) (-x_1-\ldots-9x_9)~\text{mod}~11.$$

• Thank you very much! Although I believe you solution is right (I cannot come up with a counterexample) I still can't understand the "Since $10\in (...)^*$" step. Does that mean that whatever $x_{10}$ I choose its mod 11 does not repeat? Could you please clarify it? – neek Apr 19 '12 at 14:38
• It means 10 is invertible modulo 11. – N. S. Apr 19 '12 at 14:51
• @N.S., thank you for clarifying. Now that I finally got it, I can't believe I've spent so much time on it. I think it's pathological :-) – neek Apr 19 '12 at 14:57
• I edited in some clarification. Actually you are right in a way, Neek, elements of $\mathbb{Z}/n\mathbb{Z}$ are invertible iff multiplying them by any two numbers in $\{0,\ldots,n-1\}$ does not yield the same answer mod 11. (I think that is kind of what you meant by "does not repeat", right?) – m_l Apr 19 '12 at 14:58
• It would be neater to choose $x_2, x_3 , ...$ arbitrarily - then the equation for $x_1$ is immediate. This way of doing it is easier to generalise. – Mark Bennet Apr 19 '12 at 14:59

Pick the first $9$ of the $x_i$ arbitrarily among the $10$ available choices modulo $11$. This gives $10^9$ possibilities for the first $9$ $x_i$. Now $x_{10}$ is completely determined modulo $11$, since $10$ is relatively prime to $11$. Indeed, since $10\equiv -1\pmod{11}$, we find that
$$x_{10}\equiv x_1+2x_2+3x_3+\cdots +9x_9 \pmod{11}.$$

• You did not read the question quite carefully. – akkkk Apr 19 '12 at 14:01
• Right, I thought both lists of possibilities were full. Fixed. – André Nicolas Apr 19 '12 at 14:03