Give an example of a polynomial f(x) with integer coefficient which factors (poly mod n) but which has no roots, i.e. for which there are no integers x such that f(x) ≡ 0 (mod n).

I can't find it! :( Can U help me? Thank you very much!

Printable View

- Sep 7th 2006, 02:52 AMbeta12an example of a ploynomial which factors, but has no roots
Give an example of a polynomial f(x) with integer coefficient which factors (poly mod n) but which has no roots, i.e. for which there are no integers x such that f(x) ≡ 0 (mod n).

I can't find it! :( Can U help me? Thank you very much! - Sep 7th 2006, 06:49 AMThePerfectHackerQuote:

Originally Posted by**beta12**

For thus values of $\displaystyle p$ (prime) such that, the Legendre Symbol, $\displaystyle (-1/p)=-1$, i.e. that is, $\displaystyle p=4k+3$

---

The reason why I used a prime is because $\displaystyle \mathbb{Z}_p[x]$ forms an integral domain and thus if two polynomials $\displaystyle a,b$ are such that $\displaystyle ab=0$ upon the evaluation homomorphism then $\displaystyle a=0\mbox{ or }b=0$ upon evaluation homomorphism. - Sep 7th 2006, 10:12 AMtopsquarkQuote:

Originally Posted by**ThePerfectHacker**

-Dan - Sep 7th 2006, 04:22 PMThePerfectHackerQuote:

Originally Posted by**topsquark**

- Sep 8th 2006, 02:15 PMbeta12
Hi perfecthacker,

Thks for your reply. So far I have learnt up to polynomial congruence. I haven't learnt Legendre Symbol yet.

I have tried but still can't confirm your example is a polynomial which factors, but has no roots with my current polynomial congruence knowledge.

Could you please explain your example to me with the concept of polynomail congruence? Thank you very much. - Sep 8th 2006, 02:21 PMThePerfectHackerQuote:

Originally Posted by**beta12**

$\displaystyle (x^2+1)(x^2+1)$ by definition is multiplied as,

$\displaystyle x^4+2x^2+1$

Thus, the polynomial,

$\displaystyle x^4+2x^2+1\equiv 0 (\mbox{mod }p)$

Is reducible (meaning it factors) but is has no zeros. Because, it is necessary and sufficient that,

$\displaystyle x^2+1\equiv 0(\mbox{mod }p)$

Equivalenty,

$\displaystyle x^2\equiv -1(\mbox{mod }p)$

Note, that we are claiming that there exists an $\displaystyle x$ such that is congruent to -1 modulo p. That is the same thing as saying "-1 is a quadradic residue of p" (definition). It can be shown without the Legendre Symbol that all the primes such that have -1 as a quadradic residue are 4k+1. In order, such that -1 not be a quadradic resides we require that p have form 4k+3 (because primes cannot have 4k,4k+2). - Sep 8th 2006, 02:38 PMbeta12
Thank you very much . I got it. :)

- Sep 8th 2006, 02:42 PMThePerfectHackerQuote:

Originally Posted by**ThePerfectHacker**

**Theorem**:The congruence $\displaystyle x^2+1\equiv 0(\mbox{mod } p)$ where $\displaystyle p$ is an odd prime has a solution if and only if $\displaystyle p=4k+1$.

**Proof**: Let $\displaystyle a$ solve the congruence. Thus,

$\displaystyle a^2\equiv -1(\mbox{mod } p)$

Fermat's Little Theorem,

$\displaystyle 1\equiv a^{p-1}\equiv (a^2)^{(p-1)/2}\equiv (-1)^{(p-1)/2}(\mbox{mod } p)$

If $\displaystyle p=4k+3$ then the fact,

$\displaystyle (-1)^{(p-1)/2}=1$ would not hold.

That explain the "only if" part of the theorem.

Note that,

$\displaystyle (p-1)!=1\cdot 2\cdot ...\cdot \frac{p-1}{2}\cdot \frac{p+1}{2}\cdot ...\cdot (p-2)(p-1)$

Also note that,

$\displaystyle p-1\equiv -1$

$\displaystyle p-2\equiv -2$

$\displaystyle p-3\equiv -3$

...

$\displaystyle \frac{p+1}{2}\equiv -\frac{p-1}{2}$

Thus, the factorial above can be expressed as,

$\displaystyle (p-1)!\equiv 1(-1)2(-2)3(-3)\cdot ... \cdot \frac{p-1}{2} \cdot \left( -\frac{p-1}{2} \right)$

Thus,

$\displaystyle (p-1)!\equiv (-1)^{(p-1)/2} \left( 1\cdot 2\cdot 3\cdot...\cdot \frac{p-1}{2} \right)^2 $

Wilson's Theorem,

$\displaystyle -1\equiv (-1)^{(p-1)/2} \left[ \left( \frac{p-1}{2} \right)!\right]^2(\mbox{mod } p)$.

If,

$\displaystyle p=4k+1$

Then we have,

$\displaystyle \left[ \left( \frac{p-1}{2} \right)! \right]^2\equiv -1(\mbox{mod } p)$

Which is a solution to the congruence. - Sep 9th 2006, 01:08 PMbeta12
hi perfecthacker,

Why p-1 =-1?

from your proof

p-1 =-1

p-2=-2

:

:

etc. ?

I don't get this point. Could you please explain to me. Thank you very much! - Sep 9th 2006, 04:41 PMThePerfectHacker
Hello

Quote:

Originally Posted by**beta12**

Quote:

Originally Posted by**beta12**

Quote:

Originally Posted by**beta12**

- Sep 11th 2006, 05:50 AMbeta12
Hi perfecthacker,

Thank you very much. I got it now.