Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
    
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

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
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\:.$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.