The Matiyasevich Theorem. Preliminaries

In this article, we prove selected properties of Pell’s equation that are essential to finally prove the Diophantine property of two equations. These equations are explored in the proof of Matiyasevich’s negative solution of Hilbert’s tenth problem.This work has been financed by the resources of the Polish National Science Centre granted by decision no. DEC-2015/19/D/ST6/01473.Institute of Informatics University of Białystok, Białystok, PolandMarcin Acewicz and Karol Pak. Pell’s equation. Formalized Mathematics, 25(3):197-204, 2017. doi: 10.1515/forma-2017-0019.Zofia Adamowicz and Paweł Zbierski. Logic of Mathematics: A Modern Course of Classical Logic. Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts. Wiley-Interscience, 1997.Martin Davis. Hilbert’s tenth problem is unsolvable. The American Mathematical Monthly, Mathematical Association of America, 80(3):233-269, 1973. doi: 10.2307/2318447.Yoshinori Fujisawa and Yasushi Fuwa. The Euler’s function. Formalized Mathematics, 6 (4):549-551, 1997.Xiquan Liang, Li Yan, and Junjie Zhao. Linear congruence relation and complete residue systems. Formalized Mathematics, 15(4):181-187, 2007. doi: 10.2478/v10037-007-0022-7.Robert Milewski. Natural numbers. Formalized Mathematics, 7(1):19-22, 1998.Rafał Ziobro. Fermat’s Little Theorem via divisibility of Newton’s binomial. Formalized Mathematics, 23(3):215-229, 2015. doi: 10.1515/forma-2015-0018.25431532