# How to reduce congruence power modulo prime?

If I have a congruence equation, says $$x^{15} - x^{10} + 4x - 3 \equiv 0 \pmod{7}$$

Then can I use Fermat's little theorem like this: $$(x^{6})^2 \cdot x^3 - x^6 \cdot x^4 + 4x - 3 \equiv 0 \pmod{7}$$ $$x^3 - x^4 + 4x - 3 \equiv 0 \pmod{7}$$

Update
Should it be $$x^{14}x - x^7x^3 - 4x - 3 \equiv 0 \pmod{7}$$ $$x^2x - x.x^3 - 4x - 3 \equiv 0 \pmod{7}$$ $$x^3 - x^4 - 4x - 3 \equiv 0 \pmod{7}$$ ? Thanks,

-
There are a couple of little mistakes. The $x^{14}$ is $(x^7)(x^7)$, which becomes $x^2$, so the first term should be $x^3$. And the $4x$ was turned by a typo into $-4x$. –  André Nicolas Apr 16 '11 at 4:06
@user6312: nice catch. Thank you. –  Chan Apr 16 '11 at 4:15

Not quite. Look for example at the congruence $x^6 \equiv 0 \pmod{7}$. If one assumes that $x^6 \equiv 1$, things go bad. In this case it is easy to spot that there is a problem, but perhaps in a more complicated setting one might miss it.

I would advise using the fact that $x^7 \equiv x \pmod{7}$, basically a variant of Fermat's Theorem that holds always, not just almost always.

-
I should add that when dealing with polynomial functions from $Z_p$ to $Z_p$, the procedure you mentioned can very easily lead to wrong results, while using $x^p \equiv x \pmod{p}$ is always safe. –  André Nicolas Apr 16 '11 at 3:47
@user6312: Thank you. How about my update now? –  Chan Apr 16 '11 at 3:58
@Chan: I commented on it in the wrong place, just below the problem. Of course one gets the same thing as with your original procedure, but the point is that the one I suggest always works. –  André Nicolas Apr 16 '11 at 4:09
@user6312: Many thanks. I got it now. –  Chan Apr 16 '11 at 4:16

Yes, if you're looking for solutions of the equation mod $7$ then, since $\rm\:x=0\:$ is not a solution, you can in fact deduce that $\rm\:x^6 = 1\:$. If you couldn't exclude $\rm\:x=0\:$ then you'd instead need $\rm\:x^7 = x\:.$

-
Thank you. So if $x = 0$ is one of the solution, I have to use the other form $x^p \equiv x \pmod{p}$? For example $x^2 - x \equiv 0 \pmod{7}$? –  Chan Apr 16 '11 at 3:58
@Chan: For this example, of course nothing needs to be done. The rule is that if you are solving a polynomial congruence and $0$ is not a solution, the "$x^6$" method will not lead to a mistake. The "$x^7$" method will never lead to a mistake. –  André Nicolas Apr 16 '11 at 4:13
@Chan: For a specific polynomial you can always preprocess the case $\rm\:x=0\:$. Only for a "generic" polynomial - where it's not known if 0 is a root - would you need to resort to $\rm\:x^p-x\:.$ Said in gcd-speak $\rm\ gcd(f(x),x^p-x) = gcd(f(x),x)\ gcd(f(x),x^{p-1}-1)\:.\:$ or, said structurally, $\rm \mathbb F_P[x]/(x^p-x)\ \cong \mathbb F_p + \mathbb F_p[x]/(x^{p-1}-1)\:,\:$ i.e. calculate in the two parallel universes, one where $\rm\:x=0\:$ and one where $\rm\:x^{p-1}=1\:.$ –  Bill Dubuque Apr 16 '11 at 4:19