Detecting prime numbers via roots of polynomials

Abstract

It is proved that an integer n ≥ 2 is a prime (resp., composite) number if and only if there exists exactly one (resp., more than one) nth-degree monic polynomial f with coefficients in Z _n , the ring of integers modulo n, such that each element of Z _n is a root of f. This classroom note could find use in any introductory course on abstract algebra or elementary number theory.

Keywords:

• prime number
• composite number
• congruence modulo n
• polynomial
• degree
• monic
• Euler ϕ function
• little Fermat theorem
• greatest common divisor