Simple algebra problem (fields)

[nowits]

[SOLVED] Simple algebra problem (fields)

Homework Statement

Solve x²+x+41=0 in the fields Z₄₃ and Z₁₆₇

2. The attempt at a solution
Well Z₄₃={0,1,...,42} so any y that is n=0 mod 43 works...

x²+x+41=0=43 -> x²+x=2 -> x=1

Is this how it's done or am I doing it incorrectly?

If the solution above is right, then what about the same equation in the field Z₁₆₇? I can't find any x that is in that field and solves the problem.

 

[Hurkyl]

Homework Statement

Solve x²+x+41=0 in the fields Z₄₃ and Z₁₆₇

Don't be intimidated by the fact you're working in a finite field! It's just a quadratic equation, and you've known how to solve them for a long time!

2. The attempt at a solution
Well Z₄₃={0,1,...,42} so any y that is n=0 mod 43 works...

Huh? y? n?

x²+x+41=0=43 -> x²+x=2 -> x=1

Is this how it's done or am I doing it incorrectly?

The first implication is correct (and it's an "if-and-only-if"), but you have the second one backwards. x=1 is one solution to that quadratic, but you have not proven it is the only solution.

 

[HallsofIvy]

How would you normally solve x²+ x- 2= 0? What are its roots? What do negative numbers correspond to "mod 43"?

 

[nowits]

Thanks for your answers.

But I still don't get it for Z₁₆₇:

x²+x+41=167
x²+x-126=0

$$x=\frac{-1\pm\sqrt{1-4\cdot 1\cdot(-126)}}{2}$$

The only way I get a reasonable result from that is if (under the square root):
1-4*1*(-126)=505=4
or: -126=41 => 4*1*41=164 => 1-4*1*(-126)=1-164=-163=4
or: -4*1*(-126)=504=3 => 1-4*1*(-126)=1+3=4

$$x=\frac{-1\pm\sqrt{4}}{2}=\frac{-1\pm 2}{2}$$

But then neither of the possible values of x is in Z₁₆₇.

 

[Hurkyl]

$$x=\frac{-1\pm\sqrt{4}}{2}=\frac{-1\pm 2}{2}$$

But then neither of the possible values of x is in Z₁₆₇.

You're working in Z₁₆₇, so shouldn't you use its division operator, rather than the division operator for rational numbers?

 

[nowits]

Yes, right.

I tried that but got a result that didn't solve the equation so I thought that my approach was wrong.

I tried it once again and this time got a result that works.

Ok, I've got it.

Thanks!