Primality, Equations, Congruences

Number theory is the advanced part of arithmetic dealing with specific problems on prime numbers, congruences, Diophantine equations, continued fractions, arithmetic encoding, just to mention the most famous chapters of this theory. Its topics are among the deepest and most difficult of the whole mathematics, full of open problems and intellectual challenges. Number theory is also one of the oldest mathematical subjects, because Pythagoras, Euclid, Archimedes, and Eratosthenes, were attracted by investigation in these fields. However, the most famous number theorist of antiquity surely was Diophantus of Alessandria (II century AD), and modern number theory took its first steps from Diophantus’ texts studied by Fibonacci, Pacioli, Bombelli, Viète, and Fermat, who can be considered the founder of modern number theory. Number Theory was, for a long time, considered a purely theoretical discipline, until at the end of 1900 years, it was recognized as a powerful tool in cryptography and its related applications in the transmission of information. On the line of Fermat, Mersenne, Descartes, Wallis, Newton, Leibniz, Euler, Lagrange, Legendre, Gauss, Jacobi, Dirichlet, Riemann, Hadamard, Ramanujan, Thue (without no claim of completeness) were great mathematicians active in number theory. After a fundamental discovery by Dirichlet, it resulted that this theory is intimately related to all the most important branches of mathematics, and in particular, that analysis of complex numbers reveals essential number theoretic properties. In this chapter, some basic concepts of this theory are considered from the perspective of Python algorithms, which very often express important facts in a very synthetic and effective way. ([1–7] are good texts devoted, entirely or partially, to number theory).