Primes and Bivariate Polynomials without Constant Terms: A Recursive Algorithm

We investigate the computational problem of determining whether a bivariate polynomial with non-negative coefficients and no constant term can attain a prime value. While classical conjectures such as Bouniakowsky's provide necessary conditions for univariate prime-representing polynomials, we introduce a new recursive algorithm that efficiently certifies when a bivariate polynomial form can produce no prime values at all. Our method is elementary and constructive, based on analyzing gcd-divisibility patterns arising from recursive substitutions into the polynomial. The obstruction criterion obtained leads to an efficient and elementary algorithm that certifies when a polynomial form cannot produce any prime values. The result is stronger than what is implied by the negation of Bouniakowsky's condition and applies to a wide class of polynomials, including transformations of univariate forms. We provide illustrative examples, analyze the complexity of the method, and discuss its connections to existing conjectures and possible generalizations.

K. Lakshmanan · 2024