1
$\begingroup$

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.

2 Answers 2

5

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

  • 0
    I DID PROMISE MYSELF NOT TO POST WHILE TIRED OR DISTRACTED2012-04-19
2

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

  • 0
    Right, I thought both lists of possibilities were full. Fixed.2012-04-19