2
$\begingroup$

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,

  • 0
    @user6312: nice catch. Thank you.2011-04-16

2 Answers 2

3

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.

  • 0
    @user6312: Many thanks. I got it now.2011-04-16
1

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\:.$

  • 0
    @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\:.$2011-04-16