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!
-
2$\begingroup$ It is not true that $x^{76}\equiv 1\pmod{77}$ because $77$ is not prime. $\endgroup$– Thomas AndrewsNov 3, 2013 at 22:25
-
$\begingroup$ Right, I'll apply my changes $\endgroup$– XenyalNov 3, 2013 at 22:30
-
$\begingroup$ Reread your arithmetic in the last line, something went wrong (But you are going on the right track :D) $\endgroup$– chubakuenoNov 3, 2013 at 22:48
1 Answer
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?
-
-
1
-
$\begingroup$ Just to confirm, is the final solution to the simultaneous congruence relation $x \equiv 27 \pmod{77}$? $\endgroup$– XenyalNov 5, 2013 at 3:37
-
$\begingroup$ I'm afraid you're wrong, it's $x \equiv 16 \pmod {77}$ $\endgroup$ Nov 5, 2013 at 9:36
-
$\begingroup$ Whoops arithmetic error after getting $x \equiv 1 \pmod{7}$. I turned it into $7y+2$ by accident lol. $\endgroup$– XenyalNov 5, 2013 at 21:31