Why aren't there any solutions?

Question

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 ?

Answer 1

Hint: Show that any cube is congruent to $0$ or $\pm 1$ modulo $9$.

Answer 2

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?

Answer 3

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.

Answer 4

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}$$

Answer 5

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$