Why aren't there any solutions? I am trying to find an answer to the following congruence:
$$x^{81} \equiv 95 \pmod{126}$$
And i couldn't find any soltuon but I don't know why.
First I though about the prime factorization for $126 = 2 \times 3^2 \times 7$ then I said well $gcd(x,126) =1$ in order for a solution to exits, because otherwise the $gcd(x,126)$ will not divide $95$
Then I used the euler phi function since I have now that $gcd(x,126) = 1$ and I got that $\phi(126) = \phi(2) \times \phi(9) \times \phi(7) = 1 \times 6 \times 6 = 36$
and so now I have that $$x^{36} \equiv 1 \pmod{126}$$
Now we raise to the power of $2$ so we get $$x^{72} \equiv 1 \pmod{126}$$
Now this implies that $x^{81} \equiv x^9 \pmod {126}$
Now this means that $x^{9} \equiv 95 \pmod {126}$
Now I am going in circles, I want to show that there is no solution that exists but how ?
 A: Hint: Show that any cube is congruent to $0$ or $\pm 1$ modulo $9$.
A: By Fermat's Little theorem $x^6\equiv \{0,1\}\pmod{7}$, so $x^3\equiv \{0,\pm 1\}\pmod{7}$, so $$x^{81}\equiv \left(x^{27}\right)^3\equiv \{0,\pm 1\}\not\equiv 95\equiv 4\pmod{7}$$
mod $9$ can also solve this (as André has hinted). Cubes can only be $0$ or $\pm 1$ mod $9$, because: $$(3k\pm 1)^3\equiv (3k)^3+3(3k)^2(\pm 1)+3(3k)(\pm 1)^2+\left(\pm 1\right)^3\equiv \pm 1\pmod{9}$$
A: You know that $x^{36}\equiv 1\pmod{126}$ for all $x$ coprime to $126$. So $x^9\equiv 95$ would imply $95^4\equiv 1$. Does that hold?
A: It helps to break this up using your factorization.  We may rewrite your equation as the system of equations
$$
x^9 \equiv 95 \pmod{2}\\
x^9 \equiv 95 \pmod{9}\\
x^9 \equiv 95 \pmod{7}
$$
By the Chinese remainder theorem, a solution will exist to your problem only if a solution to this problem exists.
We can reduce these equations quite a bit:
$$
x \equiv 1 \pmod{2}\\
x^3 \equiv 5 \pmod{9}\\
x^3 \equiv 4 \pmod{7}
$$
It is the second equation here that fails to have a solution.  In particular, we simply look at every residue modulo 9:
$$
0^3 \equiv 0\\
1^3 \equiv 1\\
2^3 \equiv -1\\
3^3 \equiv 0\\
4^3 \equiv 1\\
5^3 \equiv -1\\
6^3 \equiv 0\\
7^3 \equiv 1\\
8^3 \equiv -1
$$
As you can see, it is impossible to get $5$.  That is, $5$ is not a cubic residue modulo 9.
A: Hint  $\mod\! 7\!:\ \  0\not\equiv \overbrace{a^3\equiv b^2}^{\large c}\,\Rightarrow\! \overbrace{c^2}^{\large a^6\!\!}\!\!\equiv 1\equiv\!\!\overbrace{ c^3}^{\large b^6\!\!}\Rightarrow\, c\equiv 1$
