4
$\begingroup$

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!

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

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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