0
$\begingroup$

We are asked to find the solutions to the following congruence $$ x^3 + 8x^2 - x - 1 \equiv 0 \ (\text{mod } 11). $$

I know that the solution can be computed using Hensel's Lemma or by simply using brute-force. However, does there exist another approach to solving this type of problem?

$\endgroup$
1
$\begingroup$

When we have small primes $11$ for example, we can just try the first small numbers and find out the roots, let $f(x)=x^3+8x^2-x-1$ it's clear that: $$f(0)=-1,f(1)=7,f(2)=4, f(3)=7, f(4)=0 $$

and here we find the first root, and we try to factorize and obtain: $$x^3+8x^2-x-1=(x-4)(x^2+x+3)$$

and we continue testing the values $f(5)=1(25+5+3)=33=0$ and $x^2+x+3=(x-5)^2$ and we are done.

$\endgroup$
0
$\begingroup$

The Berlekamp algorithm gives, over $\mathbb{F}_{11}$ $$ x^3+8x^2-x-1=(x + 7)(x + 6)^2, $$ In an example with a degree $3$ polynomial one could also just try for a linear factor, i.e., looking for a zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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