Finding a power of x to be equivalent to some number in modular arithmetic

Question

I'm struggling to work through how to find $x$ such that $x^{11}\equiv 10\mod42$. It has been previously worked out that $11^{-1}\equiv 15\mod41$, although I'm unsure how this helps.

What I've so far tried to do is find the Euler totient $\phi (42) = 12$, thus by Euler's theorem $x^{12}\equiv 1\mod 42$. Is this to be split in to $x\cdot x^{11}\equiv 1\mod 42$?

edit: Thank you for the replies thus far. Was wondering how $11^{-1} \mod 41$ could be used as well?

Answer 1

We have $x$ even, so we can't apply Euler $\pmod{42}$ i.e., $x\equiv0\pmod2\ \ \ \ (1)$

As $42=2\cdot3\cdot7$

We need $x^{11}\equiv10\pmod3\equiv1\implies(x,3)=1$

Using Fermat's Little Theorem, $x^{3-1}\equiv1\pmod3$

$\implies x\cdot(x^2)^5\equiv1\implies x\equiv1\pmod3\ \ \ \ (2)$

Finally, $x^{11}\equiv10\pmod7\implies(x,7)=1\implies x^{7-1}\equiv1\pmod7$

$\implies10x\equiv x^{12}\equiv(x^6)^2\equiv1\pmod7$

$\iff3x\equiv1\pmod7\iff x\equiv5\pmod7\ \ \ \ (3)$

Method $\#1:$

Apply CRT on $(1),(2),(3)$

Method $\#2:$

By observation,

$x\equiv1\pmod3\equiv-2$

$x\equiv5\pmod7\equiv-2$

$x\equiv0\pmod2\equiv-2$

$\implies(x+2)\equiv0\pmod{\text{lcm}}(3,7,2)$

$\implies x+2\equiv0\pmod{42}\iff x\equiv-2\pmod{42}$

Answer 2

As you noted, $x^{12}\equiv 1\pmod {42}$ - but only if $x$ is coprime to $42$. Then splitting as you suggested as $1\equiv x\cdot x^{11}\equiv x\cdot 10\pmod{42}$ would be fine, i.e. you'd only need to find a multiplicative inverse of $10$ modiulo $42$. Alas, $10$ and $42$ are not coprime, hence $10$ has no inverse modulo $42$.

It may help to consider the single prime factors of $42$ separately (or at least treat $2$ specially as evenness of $10$ and/or $x$ seems to disturb us here). That is, solve $$\begin{align}x^{11}&\equiv 10\equiv 0\pmod{2}\\ x^{11}&\equiv 10\equiv 1\pmod{3}\\ x^{11}&\equiv 10\equiv 3\pmod{7}\\ \end{align}$$ The first immediately gives us $x\equiv 0\pmod 2$, the second (using $x^2\equiv 1$) gives us $x\equiv 1\pmod 3$, the last (using $x^6\equiv 1$) gives us $x^{-1}\equiv 3\pmod 7$, i.e., $x\equiv 5\pmod 7$. By the Chinese Remainder Theorem, this is equivalent to $x\equiv 40\pmod{42}$.