Prove that there exists at least one integer $k$ for every odd $n$ such that $x^2+x-2k$ is irreducible modulo $n$.

Question

I've tried several approaches, but none seem to get me any closer, and a solution is not available. Please help.

Answer 1

Say, no such $k$, exists.

So there exists numbers $x_1,x_2\dots ,x_{n} \in \{0,1,2,3...n\}$, such that

$x_1^2+x_1=0$ (mod n)

$x_2^2+x_2=2$ (mod n)

$x_3^2+x_3=4$ (mod n) .

.

.

. $x_{n}^2+x_{n}=2(n-1)$ (mod n)

Claim, $x_1,x_2 \dots ,x_{n}$, are all distinct, else if say $x_i=x_j$, then subtract the corresponding two equation, we will have $n|2(i-j)$, which is not possible as $n$ is odd and $|i-j|<n$, hence $\{x_1,x_2 \dots ,x_{n}\}$ is an enumeration of $\{0,1,2,3,\dots ,n-1\}$

So there exists $p,q \in \{1,2,3,\dots ,n\}$ such that $x_p=0$ and $x_q=n-1$, but $0^2+0=(n-1)^2+(n-1)$ (mod n) , hence a condradiction.

Answer 2

I believe the simplest way to solve this problem is to simply count the number of distinct polynomials of that form that factor, and see that it is less than $n$. Thus some polynomials of that form do not factor.

For every odd n, 2 is a unit modulo $n$. Thus it is sufficient to show that some $x^2+x+i$ is irreducible modulo $n$ for $i$ ranging from $0$ to $n-1$.

Suppose that all $n$ such (distinct) polynomials factored into $(x-a_i)(x-b_i)$ where $i$ ranges from $0$ to $n-1$. Then by expanding, we get $x^2+x+i = x^2 + (-a_i-b_i)x + a_ib_i$. In particular, $-a_i-b_i = 1$. Since each $b_i$ is fixed with respect to $a_i$, there can only be $n$ such pairs, corresponding to $(x-a_i)(x+a_i+1)$, where $a_i$ ranges from 1 to $n$. However, the polynomials given by $a_i = 0$ and $a_i = -1$ are both the same polynomial: $(x-0)(x+1)$. In fact, we can group each $m, -m+1$ pair in a like manner to find that the number of distinct polynomials of the form $x^2+x+i$ that factor is $(n+1)/2$. It is then easy to see that the number of distinct polynomials that do not factor is $(n-1)/2$. Since this is less than $n$, there are some polynomials that do not factor.

Answer 3

Here are some helpful facts:

1. It is sufficient to prove the property when $n$ is an odd prime.

2. A quadratic polynomial over a field is reducible exactly if it has a root.

3. The polynomials for different $k$ (modulo $n$) cannot have roots in common.

4. The polynomial for $k=0$ has two different roots.