• Support PF! Buy your school textbooks, materials and every day products Here!

Simple algebra problem (fields)

  • Thread starter nowits
  • Start date
18
0
[SOLVED] Simple algebra problem (fields)

1. Homework Statement
Solve x²+x+41=0 in the fields Z43 and Z167

2. The attempt at a solution
Well Z43={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 Z167? I can't find any x that is in that field and solves the problem.
 

Answers and Replies

Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,843
17
1. Homework Statement
Solve x²+x+41=0 in the fields Z43 and Z167
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 Z43={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
Science Advisor
Homework Helper
41,734
893
How would you normally solve x2+ x- 2= 0? What are its roots? What do negative numbers correspond to "mod 43"?
 
18
0
Thanks for your answers.

But I still don't get it for Z167:

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

[tex]x=\frac{-1\pm\sqrt{1-4\cdot 1\cdot(-126)}}{2}[/tex]

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

[tex]x=\frac{-1\pm\sqrt{4}}{2}=\frac{-1\pm 2}{2}[/tex]

But then neither of the possible values of x is in Z167.
 
Last edited:
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,843
17
[tex]x=\frac{-1\pm\sqrt{4}}{2}=\frac{-1\pm 2}{2}[/tex]

But then neither of the possible values of x is in Z167.
You're working in Z167, so shouldn't you use its division operator, rather than the division operator for rational numbers?
 
18
0
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!
 
Top