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$
3
  • 2
    $\begingroup$ It is not true that $x^{76}\equiv 1\pmod{77}$ because $77$ is not prime. $\endgroup$ Nov 3, 2013 at 22:25
  • $\begingroup$ Right, I'll apply my changes $\endgroup$
    – Xenyal
    Nov 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$
    – chubakueno
    Nov 3, 2013 at 22:48

1 Answer 1

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$
5
  • $\begingroup$ Yup! I managed to solve it (: Thanks! $\endgroup$
    – Xenyal
    Nov 4, 2013 at 1:44
  • 1
    $\begingroup$ Good. Hope my answer helped ;) $\endgroup$
    – Stefan4024
    Nov 4, 2013 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, 2013 at 3:37
  • $\begingroup$ I'm afraid you're wrong, it's $x \equiv 16 \pmod {77}$ $\endgroup$
    – Stefan4024
    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$
    – Xenyal
    Nov 5, 2013 at 21:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .