3
$\begingroup$

If possible, solve $7x^2 - 4x + 1 \equiv 0 $ (mod 11)

Not sure if I'm approaching this problem correctly, any help is appreciated.

So far I have:

$7x^2 - 4x + 1 \equiv 0 $ (mod 11)

$21x^2 - 12x + 3 \equiv 0 $ (mod 11)

$-x^2 - x + 3 \equiv 0 $ (mod 11)

$-x^2 - x \equiv -3 $ (mod 11)

$-1(x^2 + x) \equiv -3 $ (mod 11)

$(x^2 + x) \equiv 3 $ (mod 11)

-Not sure if I am heading the right way, once again any help is appreciated.

$\endgroup$
1
  • 2
    $\begingroup$ You could just plug in $x=0,1,\dots,10$. $\endgroup$ – Bill Cook Mar 21 '16 at 20:22
3
$\begingroup$

Multiply by $8$ (which is the inverse of $7$ mod $11$) and get: $x^2+x+8=0$ (mod $11$).

Then complete the square. "Half of 1" is the same as "half of 12" (mod 11) so we can rewrite our equation as $(x+6)^2-36+8=0$ (mod $11$) which simplifies to $(x+6)^2=6$ (mod $11$).

So your equation has a solution if and only if 6 is a square (mod 11).

It isn't, so there is no solution.

To show that 6 is not a square (directly) consider: $0^2=0$, $(\pm 1)^2=1$, $(\pm 2)^2=4$, $(\pm 3)^2=9$, $(\pm 4)^2=16=5$, and $(\pm 5)^2 = 25=3$ (all mod $11$).

$\endgroup$
1
$\begingroup$

The first thing I would have done is shift the $1$ to the other side, like so: $$7x^2 - 4x \equiv 10 \pmod{11}.$$ Then I would just have tried the eleven possible cases, from $x = 0$ to $x = 10$ (because for $x \geq 11$ the patterns just repeat). By this crude but effective method I would have found that there are no solutions. If the modulo was larger (say, $10000019$), I would want a more sophisticated method.

$\endgroup$
0
$\begingroup$

The situation is not really different than the one when solving a quadratic equations in the reals. You use the familiar formula and see if there exists a squareroot of the discriminant.

To that latter end you might use result on quadratic residues or check by hand.

$\endgroup$
0
$\begingroup$

In $\mathbb F_{11}$, one has $$7x^2 - 4x + 1= 0\iff-4x^2-4x+1=0\iff x(x+1)=\frac {1}{2^2}=2^8=3$$

For all $x\in\mathbb F_{11}$ we have $x(x+1)\ne 3$ (successively one has $0,2,6,1,9,8,9,1,6,2,0$)

Hence there is not solution.

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