How many solutions does the following equation have:



$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.$$

  • $\begingroup$ 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? $\endgroup$ – neek Apr 19 '12 at 14:38
  • $\begingroup$ It means 10 is invertible modulo 11. $\endgroup$ – N. S. Apr 19 '12 at 14:51
  • $\begingroup$ @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 :-) $\endgroup$ – neek Apr 19 '12 at 14:57
  • $\begingroup$ 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?) $\endgroup$ – m_l Apr 19 '12 at 14:58
  • $\begingroup$ 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. $\endgroup$ – 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}.$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.