<s>[INST] chinese remainder theorem problem in one of the steps I need to calculate the following:
$$x=8 \pmod{9}$$
$$x=9 \pmod{10}$$
$$x=0 \pmod{11}$$
I am using the chinese remainder theorem as follows:
Step 1:
$$m=9\cdot10\cdot11 = 990$$
Step 2:
$$M_1 = \frac{m}{9} = 110$$
$$M_2 = \frac{m}{10} = 99$$
$$M_3 = \frac{m}{11} = 90$$
Step 3:
$$x=8\cdot110\cdot2 + 9\cdot99\cdot9 + 0\cdot90\cdot2 = 9779 = 869\mod 990$$
I have used online calculators to check this result and I know it is wrong (it should be 539 I think) but cannot find out what am I doing wrong. Can you help me?
Thanks
 [/INST] $x \equiv -1 \pmod 9$ and $x \equiv -1 \pmod {10}.$ So $x \equiv -1 \pmod {90}$ and $x = 90 n - 1.$ But $90 = 88 + 2,$ so $90 \equiv 2 \pmod {11}.$
$$ x = 90 n - 1 \equiv 2n - 1 \pmod {11}. $$
$$ 2n \equiv 1 \pmod {11}, $$
$$ n \equiv 6 \pmod {11}. $$
Start with $n=6,$ so $x = 540 - 1 = 539.$
$$ \bigcirc   \bigcirc  \bigcirc  \bigcirc  \bigcirc   \bigcirc  \bigcirc  \bigcirc  $$
A more official way to combine the $90$ and $11$ parts is this: the continued fraction for $90/11$ has penultimate convergent $41/5,$ and
$$ 41 \cdot 11 - 5 \cdot 90 = 1. $$
So 
$$ 451 \equiv 1 \pmod {90}, \; \; 451 \equiv 0 \pmod {11},  $$
$$ -450 \equiv 0 \pmod {90}, \; \; -450 \equiv 1 \pmod {11}.  $$
We want something $-1 \pmod {90}$ and $0 \pmod {11},$ so we can ignore the second pair and use
$$ -451 \equiv -1 \pmod {90}, \; \; -451 \equiv 0 \pmod {11}.  $$
Also note
$$ 990 - 451 = 539. $$
Let's see: the virtue of the continued fraction thing is that, when i want something $A \pmod {90}$ but $B \pmod {11},$ I just take $451 A -450 B.$
</s>