Determine all solutions of the congruence relation $2x^{121} + 22x^{36} + 21x^{30} + 2 \equiv 0 \pmod {77}$

My solution so far is as follows: Using the Chinese Remainder Theorem, we can simplify the congruence to the simultaneous congruence of: $$\mathrm{Simultaneously: }\ \ \begin{cases} 2x^{121}+22x^{36}+21x^{30}+2 \equiv 0 \pmod 7 \\ 2x^{121}+22x^{36}+21x^{30}+2 \equiv 0 \pmod {11} \\ \end{cases}$$ Using modular arithmetic, we simplify the first congruence to $2x+3 \equiv 0 \pmod 7$ and find that $x \equiv 2 \ \pmod 7$ is a solution. The second part of the congruence is where I have problems; after using Fermat's Little Theorem on $\pmod{11}$, does the congruence simplify to $2x^{6}+2x+3 \equiv 0 \pmod {11}$? Any help would be appreciated!

• It is not true that $x^{76}\equiv 1\pmod{77}$ because $77$ is not prime. – Thomas Andrews Nov 3 '13 at 22:25
• Right, I'll apply my changes – Xenyal Nov 3 '13 at 22:30
• Reread your arithmetic in the last line, something went wrong (But you are going on the right track :D) – chubakueno Nov 3 '13 at 22:48

Your idea of simplyfication is OK, but it seems that you've concetrated on the exponents, so you've missed something obvious.

After the split, the two congruence relations are:

$$2x^{121} + 22x^{36} + 21x^{30} + 2 \equiv 2x + 1 + 2 \equiv 2x + 3 \equiv 0 \pmod 7$$ $$2x^{121} + 22x^{36} + 21x^{30} + 2 \equiv 2x + 21 + 2 \equiv 2x + 1 \equiv 0 \pmod {11}$$

Using simply application of Fermat's Little Theorem and the fact that $22 \equiv 0 \pmod {11}$. Now it's just simple system of linear modular equations. Can you continue on your own now?

• Yup! I managed to solve it (: Thanks! – Xenyal Nov 4 '13 at 1:44
• Good. Hope my answer helped ;) – Stefan4024 Nov 4 '13 at 1:44
• Just to confirm, is the final solution to the simultaneous congruence relation $x \equiv 27 \pmod{77}$? – Xenyal Nov 5 '13 at 3:37
• I'm afraid you're wrong, it's $x \equiv 16 \pmod {77}$ – Stefan4024 Nov 5 '13 at 9:36
• Whoops arithmetic error after getting $x \equiv 1 \pmod{7}$. I turned it into $7y+2$ by accident lol. – Xenyal Nov 5 '13 at 21:31