Solving for Congruence Class

Question

I’m trying to solve the following problem:

Find all solutions to [11][x]^46 + [45][x]^11 = [4] in Z55 with 0 <= x < 55.

Can anyone please tell me how to solve this?

Answer 1

Hint: What do you get when you take mod 11 and mod 5?

$x \equiv x^{11} \equiv 4 \pmod{11} $. This has solutions $ x \equiv 4 \pmod{11}$.
$x^2 \equiv x^{46} \equiv 4 \pmod{5} $. This has solutions $ x \equiv 2, 3 \pmod{5}$.

Answer 2

If $11x^{46}+45x^{11}\equiv4\bmod55$, then $x^{46}\equiv4\bmod 5$ and $x^{11}\equiv4\bmod11$.

But from Fermat's little theorem, we know $x^{11}\equiv x\bmod 11.$

Also $x\not\equiv0\bmod 5,$ or else we'd have $x^{46}\equiv0\bmod5$,

so $x^4\equiv1\bmod5$, so $x^{46}\equiv x^2\bmod5$.

Since $x^{2}\equiv4\bmod5$, we have $x\equiv\pm2\bmod5$.

So $x\equiv4\bmod11$ and $x\equiv\pm2\bmod5$. Do you know how to solve that mod $55$?

Answer 3

Put $\,p=5,\, a=2,\, T=46\,$ below, which highlights innate structure enabling the simple solution, i.e. by CRT it is equivalent to $\,x^2\equiv a^2\pmod{\!p},\ x\equiv a^2 \pmod{\!q}\,$ which is easily solvable as below.

Theorem $ $ If $\,p\,$ and $\,q = 2p+1\,$ are primes and $\,\color{#c00}{T\equiv 2}\pmod{p\!-\!1}$

$\qquad\qquad\ \bmod pq\!:\,\ \ a^2 \equiv\, q\, x^{\color{#c00}T} - 2p\, x^{\large q} \iff x\equiv a^2\color{#0a0}{-(a^2\pm a)}q$

Proof $ $ Applying CRT = Chinese Remainder Theorem and little Fermat we have

$\!\!\bmod q\!:\ {-2}p\equiv 1\,$ so $\ a^2 \equiv 0+1\cdot x^{\large q}\equiv\, x\iff x =\color{#90f}{ a^2\!+\!j\,q}\ $ for $\,j\in\Bbb Z$

$\!\!\bmod p\!:\ \ \ \ \ \ q\equiv 1\,$ so $\,a^{2}\equiv 1\cdot x^{\large\color{#c00}2}-0\!\!\iff\! \pm a\equiv x\equiv \color{#90f}{a^2\!+\! \color{#0a0}j\,q} \equiv a^2\!+\!j\!\iff\! \color{#0a0}{j\equiv \pm a -a^2}$