Computational Methods in Discrete Mathematics

Experimental program estimation for the quantity of prime numbers necessary for elimination of polynomial equations without integer roots

Yu. L. Zachesov, N. P. Salikhov


Abstract: This work deals with a way of eliminating polynomial equations in a single unknown without integer roots with their right parts' known spectrum determined by estimation based on the difference between the polynom's maximum and minimum values in a certain interval. Ideas introduced by Gauss and developed to the case of any prime numbers and any residues were used to elaborate this method. The solutions of congruence in a single variable which demonstrate the elimination method potential are also given. A program in the packet of symbolic calculations is offered for the experimental estimation of the necessary length of the prime numbers list used for equation elimination. The use of a shorter list allows to expect the algorithm's time complexity reduction when this elimination is applied.

UDC: 519.61