I recently learned of the following connection between prime numbers and prime polynomials in the field of cardinality $2$. Namely, you take a natural number $n$, and use the digits of the base $2$ representation of $n$ to construct a polynomial $P(x)$ over the $2$-element field. It is a theorem that $n$ is prime precisely when the corresponding $P(x)$ is a prime polynomial. I wonder, does this hold true for other prime bases $b$ and the corresponding finite field of $b$ elements? Meaning, if you take a natural number $n$, and use the digits of the base $b$ representation of $n$ to construct a polynomial $P(x)$ over the $b$-element field, is it then the case that $n$ is prime precisely when $P(x)$ is a prime polynomial? If not for all prime bases, is it true for at least some prime bases? Or is it in fact true only for base $2$?
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ The asserted theorem is not true in base $2$. For example, the polynomials corresponding to the primes $n=17$ and $n=23$ are the reducible polynomials $x^4+1=(x+1)^4$ and $x^4+x^2+x+1=(x+1) (x^3+x^2+1)$, respectively. Meanwhile, the polynomial corresponding to the composites $n=25$ and $n=55$ are the irreducible polynomials $x^4+x^3+1$ and $x^5+x^4+x^2+x+1$, respectively. $\endgroup$– Greg MartinCommented May 7 at 22:16
-
2$\begingroup$ The converse is Cohn's irreducibility Test. Follow the link for general results on such matters. $\endgroup$– Bill DubuqueCommented May 7 at 23:30
Add a comment
|