Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
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
show 2 more comments

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

share|improve this answer
    
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
    
Thank you for your help! –  Neek Apr 19 '12 at 14:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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