Quadratic Irreducible Polynomials and A Beautiful Partition of Pime Numbers
Now we turn our attention to quadratic irreducible polynomials over \(\mathbf{F}_p\) where $p$ is an odd prime. $x^2-1$ has only two divisors of order two, namely $x+1$ and $x^2-1$. In the case of $f(x)=x+1$, $\alpha$ is in the kernel of $f(\sigma)$ iff $\sigma(\alpha)=-\alpha$ so that $P_\alpha=(x-\alpha)(x+\alpha)=x^2-\alpha^2$. Since $P_\alpha$ is irreducible $\alpha notin\mathbf{F}_p$. It follows that every irreducible based on $x+1$ is of the form $P=x^2+c$ where $c$ is the negative a quadratic nonresidue, i.e., $-c$ is not a perfect square. The quadratic nonresidues can be easily obtained using Euler's Criterion, namely, $a$ is a quadratic residue if $a^{\bar p}=1$ where throughout $\bar p=\frac{p-1}{2}$. Moreover, $a$ is a quadratic nonresidue iff $a^{\bar p}=-1$. Let $Res$ and $NRes$ denote the set of residues and nonresidues respectively. Here there two cases $\bar p$ is odd or even. In the first case, i.e. when $\bar p$ is odd, $-1\in NRes$ so that in this case $-NRes=Res$. When $\bar p$ is even, we have $-1\in Res$ so that $-NRes=NRes$.
We ask: are there any primitive irreducibles of the form $P_c=x^2+c$? To answer this question we will show there is a nice connection bewteen $\text{ord}P_c$, the order of $P_c$ i.e. the order of x in $(\mathbf{F}_p[x]/P_c)^*$ and
$\text{ord} c$, the order of $c$ in $\mathbf{F}_p^*$. First it is easily verified that in the first ring, $x^{2n}=(-c)^n$ and $x^{2n+1}=(-c)^nx.$ Let $\alpha=\text{ord} c$ then $c^\alpha=1$ so that $x^{2\alpha}=(-1)^\alpha$.
When $\bar p$ is odd , $-NRes=Res$ is group of odd order. In this case, $x^{2\alpha}=-1$. It follows that $\text{ord }P_c=4\text{ord } c$ when $\bar p$ is odd.
If for some $m$, $c^{2m+1}=1$ then $c^{2m}c=1$ so that $c=(c^{-m})^2$ and as such is a quadratic residue. Thus, when $\bar p$ is even so that $-NRes=NRes$, $\text{ord }c$ must be even too. We have $x^{2\alpha}=1$. Thus, we have shown that
$Res$ is a subgroup of order $\bar p$ which is less than $p-1$, and therefore, does not contain any primitive elements. Thus depending on $\bar p$ being even or odd all primitve elements of $\mathbf{F}_p^*$ are in the list of the constant terms of the $P_c$'s or none are. When $\bar p$ is odd a $c$ that generates the group $Res$ has order $\bar p$ so that $P_c$ has order $4\bar p=2(p-1)$. When $\bar p$ is even so that a primitive $c$ exists, $P_c$ has order $2(p-1)$. In either case, the maximal order of $P_c$ is $2(p-1)$, the answer to our question is negative: None of $P_c=X^2+c$ are primitive.
After obtaining all irreducibles of the form $P_c=X^2+c$, and noting that none of them are primitive, we observe that a horizontal translation of each of these: $(x+b)^2+c$ does not have a root either. Otherwise, its translation would be a root of $P=x^2+c$. There are $\bar p$ irreducibles of the form $P=x^2+c$ because there are that many quadratic nonresidues, or alternatively note that $\Phi(x+1)=p-1$ .
Next, consider the normal irreducibles, namely those resulting from the divisor $x^2-1$. Clearly $\Phi(x^2-1)=(p-1)^2$, so that the number of normal irreducibles is $\bar{p}(p-1)$. Since there are exactly the same number of horizontal translations all (normal) irreducibles are thus obtained.
We now look at an example in detail: the case $p=17$. Here $\bar p=8$ and residues are [1 2 4 8 9 13 15 16]. Negatives of nonresidues are [3 5 6 7 10 11 12 14]. The irreducibles are listed below.
| Irreducible | Range | Multiplicity |
|---|---|---|
| $X^2+3$ | [1 2 3 4 5 7 11 12 16] | 1 |
| $X^2+5$ | [1 3 4 5 6 7 9 13 14] | 3 |
| $X^2+6$ | [2 4 5 6 7 8 10 14 15] | |
| $X^2+7$ | [3 5 6 7 8 9 11 15 16] | |
| $X^2+10$ | [1 2 6 8 9 10 11 12 14] | 3 |
| $X^2+11$ | [2 3 7 9 10 11 12 13 15] | |
| $X^2+12$ | [3 4 8 10 11 12 13 14 16] | |
| $X^2+14$ | [1 5 6 10 12 13 14 15 16] | 1 |
The list of primitives $(X+b)^2+c$ for the first 100 odd primes is $p(b,c)$ as follows
3(1,1) 5(1,2) 7(2,1) 11(4,1) 13(2,2) 17(2,3) 19(3,1) 23(2,1) 29(1,2) 31(4,1) 37(4,2) 41(2,3) 43(2,1) 47(2,1) 53(1,2) 59(3,1) 61(2,2) 67(7,1) 71(8,1) 73(3,5) 79(6,1) 83(10,1) 89 (2,3) 97(4,5) 101(1,2) 103(2,1) 107(2,1) 109(2,2) 113(4,3) 127(8,1) 131(3,1) 137(8,3) 139(4,1) 149(3,2) 151(9,1) 157(2,2) 163(7,1) 167(2,1) 173(1,2) 179(3,1) 181(4,2) 191(10,1) 193 (5,5) 197(3,2) 199(13,1) 211(4,1) 223(2,1) 227(2,1) 229(2,2) 233(8,3) 239(8,1) 241(7,7) 251(5,1) 257(2,3) 263(2,1) 269(9,2) 271(5,1) 277(2,2) 281(4,3) 283(2,1) 293(1,2) 307(9,1) 31 1(4,1) 313(3,5) 317(10,2) 331(6,1) 337(19,5) 347(4,1) 349(4,2) 353(7,3) 359(11,1) 367(3,1) 373(2,2) 379(3,1) 383(2,1) 389(1,2) 397(2,2) 401(4,3) 409(10,7) 419(4,1) 421(4,2) 431(4,1) 433(3,5) 439(9,1) 443(2,1) 449(16,3) 457(5,5) 461(8,2) 463(2,1) 467(2,1) 479(4,1) 487(3,1) 491(5,1) 499(3,1) 503(6,1) 509(1,2) 521(2,3) 523(2,1) 541(4,2) 547(2,1)
The graph of $b$'s is given below.
Note $c$'s only take on prime numbers. Here is the proof. As usual there are two cases. When $\bar p$ is odd $NNRes=Res$ and always contains 1 as the smallest element. (Throught we use positive integers as represenatives.) So, suppose $\bar p$ is even so that $NNRes=NRes$. Let $a$ be the smallest positive representative element of this set. If $a=a'a''$ is a proper decomposition of $a$ then $a'$ and $a''$ do not belong to $NRes$ and therefore they both belong to $Res$. The latter is a group so that the product namely $a$ belongs to $Res$, contradicting the choice of $a$. Therefore the smallest element of $NNRes$ is prime.
Now that we know the $c$'s are 1 or prime, given the characterictic $p$, we can use quadratic reciprocity to find the the $c$'s quickly. The result follows.
(C=1 ) 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179, 191, 199, 211, 223, 227, 239, 251, 263, 271, 283, 307, 311, 331, 347, 359, 367, 379, 383, 419, 431, 439, 443, 463, 467, 479, 487, 491, 499, 503, 523, 547, 563, 571, 587, 599, 607, 619, 631, 643, 647, 659, 683, 691, 719, 727, 739, 743, 751, 787, 811, 823, 827, 839, 859, 863, 883, 887, 907, 911, 919, 947, 967, 971, 983, 991, 1019, 1031, 1039, 1051, 1063, 1087, 1091, 1103, 1123, 1151, 1163, 1171, 1187, 1223.
(C=2 ) 5, 13, 29, 37, 53, 61, 101, 109, 149, 157, 173, 181, 197, 229, 269, 277, 293, 317, 349, 373, 389, 397, 421, 461, 509, 541, 557, 613, 653, 661, 677, 701, 709, 733, 757, 773, 797, 821, 829, 853,877, 941, 997, 1013, 1021, 1061, 1069, 1093, 1109, 1117, 1181, 1213, 1229.
(C=3 ) 17, 41, 89, 113, 137, 233, 257, 281, 353, 401, 449, 521, 569, 593, 617, 641, 761, 809, 857, 881, 929, 953, 977, 1049, 1097, 1193, 1217.,
(C=5 ) 73, 97, 193, 313, 337, 433, 457, 577, 673, 937, 1033, 1153.
(C=7 ) 241, 409, 601, 769.
(C=11 ) 1009, 1129, 1201
Totals are [101 53 27 12 4 3 0 0 0 0]
From observing the above data, we arrive at the following result.
Let $\mathbf{P}$ be the set of primes. Let $A_1=\{p\in \mathbf{P}| \quad (p-1)/2\quad \text{is odd}\}$ then $A_1$ has Dirichlet density $\text{d}A_1=\frac{1}{2}$, in particular, $A_1$ is infinite. Moreover, for the $n\text{th}$ prime $q$, let $A_q=\{p\in \mathbf{P}| \quad q\quad \text{is the first positive square nonresidue mod } p\}$, then $\text{d}(A_q)=2^{-(n+1)}$ and $\mathbf{P}$ is the disjoint union of $A_1$ and the $A_q$'s.
In fact, we can do better. For now, note that $A_1=P(4,3)$ is a Dirichlet set in the sense that we will say a subset of Primes is a Dirirchlet Set iff it is of the form $P(a,b)=\{p\in\mathbf{P}|\quad p=_a b\}$ with $a$ and $b$ relatively prime. By his theorem $\text{d}P(a,b)=\Phi(a)^{-1}$. In particular, $\text{d}A_1=\frac{1}{2}$.
Next, note that $A_2=\{p\in \mathbf{P}| \quad p=_4 1 \quad \text{and} \quad \big(\frac{2}{p}\big)=-1\}$. It is known that $\big(\frac{2}{p}\big)=(-1)^{\frac{p^2-1}{8}}$. So, if we write $p=4n+1$ then $p^2-1=4n(4n+2)$ so that $\frac{p^2-1}{8}=n(2n+1)$. Since $2n+1$ is odd, $\big(\frac{2}{p}\big)=-1$ iff $n$ is odd say $n=2k+1$. Then $p=4(2k+1)+1=8k+5$. In other words, $A_2=P(8,5)$ is a Dirichlet set with density $\frac{1}{\Phi(8)}=\frac{1}{4}$ and $A_2'=_{\text{def}}\bigcup_{n>2}\quad A_{q_n}=P(1,8)$. Not all $A_q$'s are Dirichlet sets but the next best thing is true. Namely, that each $A_q$ is a finite disjoint union of Dirichlet sets. We will calculate this later, but for now note the following charaterization of the $A_q$'s in terms of Legendre symbols.
Let $ \mathbf{P}'=\{p\in \mathbf{P}| \quad p=_4 1 \quad \}$ and $q_i$ denote the $i$th prime. Then for $p$ in $ \mathbf{P}'$, $\frac{p-1}{2}$ is even so that by quadratic reciprocity $\big(\frac{q_i}{p}\big)=\big(\frac{p}{q_i}\big)$ for all $i$. We have
From the above charcterization it is clear that
Next we turn to the problem of describing the $A_q$'s as a finite disjoint union of Dirichlet sets. We have already seen that $A_2=P(8,5)$. We have $A_3=P(24,17)$, also $24=4\times 2\times 3$ and $\text{d}A_3=\Phi(24)^{-1}=\frac{1}{8}$. Next,
The general case is as follows. Let $a_n=4q_1\dots q_n$, then $\Phi(a_n)$ is divisible by $2^{(n+1)}$. Put $c_n=\Phi(a_n)/2^{(n+1)}$ and let $b_1, \dots, b_{c_n}$ be the first $c_n$ elements of $A_n$. We have
In practice, one consequence of these densities is that for the first 200 primes we need only to go up to $A_{11}$, in symbols, $P_{200}=A_1\bigcup A_2\bigcup A_3\bigcup A_5\bigcup A_7\bigcup A_{11}$ and for the first 1000 primes we only need to go up to $A_{13}$, i.e.,
Before we prove the above assertions, it is instructive to to show how the first few sets are calculated. We have already seen how $A_2=P(8,5)$ and $A_3'=P(8,1)$.
For $A_3$, note that $NRes_3=\{2\}$ so that $x\in A_3$ iff $x\in A_2'$ and $x=_32$ iff $x_8=1$ and $x=3m+2$ so that $1=_83m+2$. Further more 3 and 8 are relatively prime so that 3 is invertible in $\mathbf{Z}_8$, and in fact, is its own inverse. We have $m=_8-3=_85$, i.e. $m=8k+5$. Substituting back, we have $x=3(8k+5)+2=24k+17$. We have proved $A_3=P(24,17)$. A similar calculation using $Res_3$ instead shows that $A_3'=P(24,1)$.
For $A_5$, note that $NRes_5=\{2,3\}$ has two elements there are two cases resluting in two Dirichlet sets.
First, $x\in A_3'$ and $x=_52$ iff $x_24=1$ and $x=5m+2$ so that $1=_{24}3m+2$. Further more 5 and 24 are relatively prime so that 5 is invertible in $\mathbf{Z}_{24}$, and in fact, is its own inverse. We have $m=_{24}-5=_{24}19$, i.e. $m=24k+19$. Substituting back, we have $x=5(24k+19)+2=120k+97$. We get $P(120,97)$.
Second, A similar calculation with $x=5m+3$ results in $P(120,73)$.
Using $Res_5$ gives the pieces of $A_5'$. We have shown
For $A_7$, the calculations are alike except for a small detail. When considering
the case $x=_{120}1$ and $x=7m+5$, we get $x=840k+481$ and $481$ is not prime
but adding 840 (or multiples thereof if need be) results in the prime 1321. Below is
the result of these calculations.
By the way, the fact that initial numbers in $A_7'$ are squares of primes is a coincidence that does not hold for $A_{11}'$.
Finally, we are ready to state and prove our theorem.
THEOREM. Let $a_n=4q_1\dots q_n$ and note that $2^{(n+1)}$ divides $\Phi(a_n)$. Put $c_n=2^{-(n+1)}\Phi(a_n)$. Then there are primes $p_1,\dots,p_{c_n}$ in $A_{q_n}$ and $b_1,\dots,b_{c_n}$ in $\mathbf{N}$ such that
PROOF. The proof is by induction on $n$. We assume the theorem for $n$ and prove it for $n+1$. To this end, let $q=q_{n+1}$, $a=a_{n+1}$ and $c=c_{n+1}$. Then $a=a_nq$ and \begin{equation*} \begin{split} \phi(a) = & 4a_1\dots a_nq\big(\frac{q_1-1}{q_1}\big)\dots \big(\frac{q_n-1}{q_n}\big)\big(\frac{q-1}{q}\big) \\ = & \phi(a_n)(q-1)=2^{(n+1)}c_n(q-1)=2^{(n+2)}c\bar q, \end{split} \end{equation*} where $\bar q=\frac{q-1}{2}$ and $c=2^{-(n+2)}\phi(a)$ then $c=c_n\bar q$. \par Now $|Res_q|=|NRes_q|=\bar q$. Write $NRes_q=\{m_1,\dots,m_{\bar q}\}$. For $x\in P(a_n,b_i)$ such that $x=_qm_j$, we have \begin{equation} x=_{a_n}b_i \qquad\text{and}\qquad x=qm+m_j \end{equation} Therefore, $qm=_{a_n}b_i-m_j$. Since $q$ and $a_n$ are relatively prime, $q$ is invertible in $\mathbb{Z}_{a_n}$. So, $m=_{a_n}q^{-1}(b_i-m_j).$ Let $\bar m_j$ be a positive representative of $q^{-1}(b_i-m_j)$ that is less than $a_n$, then $m=ka_n+\bar m_j$ which we substitute back in (3.3) to get $$x=q(ka_n+\bar m_j)+m_j=ak+q\bar m_j+m_j.$$ In most cases, $q\bar m_j+m_j$ is already prime. But if not, let $\bar p_j$ be the first $k'$ such that $\bar p_j=ak'+q\bar m_j+m_j$ is prime. We have $x\in P(a,p_j).$ There are $c_n$ Dirichlet sets forming $A_{q_n}$, each resulting in $|NRes_q|=\bar q$ new Dirichlet sets $P(a,p_j).$ In total, we have $c_n\bar q=c$ new sets, i.e. $A_q=\bigcup_{i=1}^{c} P(a_n,p_i)$ and since the union is disjoint the densities add. We have $$\text{d}A_q=c\frac{1}{\phi(a_n)}=2^{-(n+2)},$$ as desired. \par Finally, we need the result for $A_q'$. This is done with a similar calculation but using $Res_q=\{r_1,\dots,r_{\bar q}\}$ instead. As before, let $\bar r_j$ be a positive representative of $q^{-1}(b_i-r_j)$ that is less than $a_n$, then $m=ka_n+\bar r_j$ and $x=ak+q\bar r_j+r_j.$ Put $\bar b_j=q\bar r_j+r_j.$ Then $A_q'=\bigcup_{i=1}^{c} P(a_n,b_i)$. The proof is complete.
.
.
.
.