# Modular arithmetic - Polynomials

• Mar 14th 2011, 09:09 AM
Darkprince
Modular arithmetic - Polynomials
Sorry for bothering again, I have thee questions. I did the first two ones and just want a verification of my answers and guidance for solving the third question.

1) Find all the solutions of x^2+2x+4=0 in Z/6Z

Solution: Let f(x)=x^2+2x+4=0 then only f(2)=12 is congruent to 0 (mod 6) so x=2 is the only solution.

2) Find all prime numbers p such that x+2 is a factor of x^4+x^3+x^2-x+1 in Fp[x]

Solution: Let f(x)=x^4+x^3+x^2-x+1. If x+2 is a factor of f(x) then f(2) is congruent to 0 (mod p), p a prime number

f(2)=27 so we must find the prime numbers that divide 27, so p=3 is the only solution

3) Find all the positive integers n such that x^2+3 divides x^5-10x+12 in (Z/nZ) [x]

If someone can check my answers for question 1 and 2 and give me an answer for question 3 I would appreciate it. Thanks in advance!
• Mar 14th 2011, 09:17 AM
TheChaz
1. f(2) = 12 = 0, so 2 is a solution, but that might not be enough (for your teacher, at least) to just say "this is the only solution".
You could just show your work for f(0), f(1), f(3), f(4), and f(5). (Hopefully that will add about 4 lines!)

2. Uh oh! When (x + 2) is a factor, then f(-2) = 0 !!! Rework this one, with that slight change.

3. Have you tried long division?
• Mar 14th 2011, 09:21 AM
Darkprince
Thank you. For qn 1 I showed my working, for question 2 f(-2)=15 so p=3, p=5.
For qn 3 how to do a long division reducing modulo n if we don't know n? Thanks again!

Ok, I did a long division and found that x^5-10x+12=(x^2+3)*(x^3-3x)-x+12, i.e my remainder is -x+12
How can I proceed from that? Thank you again!
• Mar 14th 2011, 09:48 AM
TheChaz
First you do the long division (!).
Then the remainder (which Wolfram claims to be 12 - x) should equal/be congruent to zero. Then... you're almost there!
• Mar 14th 2011, 09:52 AM
Darkprince
So x=12 implies n=12 is the only poaitive integer n such that x^2+3 divides x^5-10x+12??
• Mar 14th 2011, 09:56 AM
TheChaz
We are solving 12 = 0 (mod n) for n > 0
So how about the factors of 12???
• Mar 14th 2011, 10:01 AM
topsquark
Quote:

Originally Posted by Darkprince
Sorry for bothering again, I have thee questions. I did the first two ones and just want a verification of my answers and guidance for solving the third question.

1) Find all the solutions of x^2+2x+4=0 in Z/6Z

Solution: Let f(x)=x^2+2x+4=0 then only f(2)=12 is congruent to 0 (mod 6) so x=2 is the only solution.

2) Find all prime numbers p such that x+2 is a factor of x^4+x^3+x^2-x+1 in Fp[x]

Solution: Let f(x)=x^4+x^3+x^2-x+1. If x+2 is a factor of f(x) then f(2) is congruent to 0 (mod p), p a prime number

f(2)=27 so we must find the prime numbers that divide 27, so p=3 is the only solution

3) Find all the positive integers n such that x^2+3 divides x^5-10x+12 in (Z/nZ) [x]

If someone can check my answers for question 1 and 2 and give me an answer for question 3 I would appreciate it. Thanks in advance!

The first two looks good to me. :)

For the third I would make the division:
$\displaystyle \frac{x^5 - 10x + 12}{x^2 - 3} = x^3 - 3x - \frac{x - 12}{x^2 + 3}$

For what x (mod n) is x - 12 = 0?

-Dan

Wow. A lot happened as I was writing this!
• Mar 14th 2011, 10:07 AM
Soroban
Hello, Darkprince!

I have another approach to #1 . . .

Quote:

$\text{(1) Find all the solutions of: }\, x^2+2x+4\:\equiv\:0\:\text{ (mod 6)}$

$\text{Since }2\:\equiv\:-4\text{ (mod 6)}$

. . $\text{the equation becomes: }\:x^2 - 4x + 4 \:\equiv\:0\text{ (mod 6)}$

$\text{Then we have: }\:(x-2)^2 \:\equiv\:0\text{ (mod 6)} \quad\Rightarrow\quad x-2 \:\equiv\:0\text{ (mod 6)}$

. . $\text{Therefore: }\:x \:\equiv\:2\text{ (mod 6)}$

• Mar 14th 2011, 10:14 AM
Darkprince
Thanks but why are we solving 12 = 0 (mod n) for n > 0? I just don't see the point, sorry for asking again!
• Mar 14th 2011, 10:19 AM
topsquark
Quote:

Originally Posted by Darkprince
Thanks but why are we solving 12 = 0 (mod n) for n > 0? I just don't see the point, sorry for asking again!

The remainder of the long division has the numerator x - 12 for any n. The only way to make the remainder 0 then, is to let x - 12 = 0 (mod n).

-Dan
• Mar 14th 2011, 10:19 AM
TheChaz
Quote:

Originally Posted by topsquark
...
Wow. A lot happened as I was writing this!

We also solved the general quintic. Where were you?!?

But seriously, forks...

We want the remainder to "equal" zero.
The remainder is (congruent to) 12. So we want 12 to "equal" zero.
12 = 0 (mod 1) ... in a lame ("trivial") kind of way
12 = 0 (mod 2)
12 = 0 (mod 3)
12 = 0 (mod ....)

(edit: apparently a lot happened while *I* was writing! ;) )
• Mar 14th 2011, 11:00 AM
topsquark
Quote:

Originally Posted by TheChaz
We also solved the general quintic. Where were you?!?

Coming up with a more intuitive method for solving the four color theorem.

-Dan
• Mar 14th 2011, 11:22 AM
Darkprince
Thank you all for the answers. I am yet trying to understand the logic behind this. The remainder is -x+12 for any n. But we want a zero remainder, so -x+12=0 =>x=12. After that I am a bit confused! Thanks again for any help!!
• Mar 14th 2011, 01:12 PM
topsquark
Quote:

Originally Posted by Darkprince
Thank you all for the answers. I am yet trying to understand the logic behind this. The remainder is -x+12 for any n. But we want a zero remainder, so -x+12=0 =>x=12. After that I am a bit confused! Thanks again for any help!!

Again, we are working in mod n, so we need x = 12 (mod n). Is 12 the only solution for x? (For an example, what if n = 2?)

-Dan
• Mar 14th 2011, 03:35 PM
Darkprince
n can be 1,2,3,4,6,12 right? Thanks for the help guys I think I figured it out :)