## Number Theory for dummies

Miscellaneous pages

Algebra | coordinate geometry | Topology for dummies | Symmetry | Bertrand Russell philosophy | Sir issac newton | Topology for dummies | Albert Einstein

Number theory for dummies

Euler's interest in number theory can be traced to the influence of Christian Goldbach, his friend in the St. Petersburg Academy. A lot of Euler's early work on number theory was based on the works of Pierre de Fermat. Euler developed some of Fermat's ideas, and disproved some of his conjectures. Euler linked the nature of prime distribution with ideas in analysis. He proved that the sum of the reciprocals of the primes diverges. In doing so, he discovered the connection between the Riemann zeta function and the prime numbers; this is known as the Euler product formula for the Riemann zeta function. Euler proved Newton's identities, Fermat's little theorem, Fermat's theorem on sums of two squares, and he made distinct contributions to Lagrange's four-square theorem. He also invented the totient function φ(n) which is the number of positive integers less than or equal to the integer n that are coprime to n. Using properties of this function, he generalized Fermat's little theorem to what is now known as Euler's theorem. He contributed significantly to the theory of perfect numbers, which had fascinated mathematicians since Euclid. Euler also conjectured the law of quadratic reciprocity. The concept is regarded as a fundamental theorem of number theory, and his ideas paved the way for the work of Carl Friedrich Gauss. By 1772 Euler had proved that 231 − 1 = 2,147,483,647 is a Mersenne prime. It may have remained the largest known prime until 1867.

Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study
of the integers. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathematics is the queen of the sciences—and number
theory is the queen of mathematics."[1] Number theorists study prime numbers as well as the properties of objects made out of
integers (for example, rational numbers) or defined as generalizations of the integers (for example, algebraic integers).

Integers can be considered either in themselves or as solutions to equations (Diophantine geometry).
Questions in number theory are often best understood through the study of analytical objects
(for example, the Riemann zeta function) that encode properties of the integers, primes or other
number-theoretic objects in some fashion (analytic number theory). One may also study real numbers
in relation to rational numbers, for example, as approximated by the latter (Diophantine approximation).

The older term for number theory is arithmetic. By the early twentieth century, it had been superseded by "number theory".
(The word "arithmetic" is used by the general public to mean "elementary calculations"; it has also acquired other meanings
in mathematical logic, as in Peano arithmetic, and computer science, as in floating point arithmetic.) The use of the term
arithmetic for number theory regained some ground in the second half of the 20th century, arguably in part due to French influence.
In particular, arithmetical is preferred as an adjective to number-theoretic.

Eusebius, PE X, chapter 4 mentions of Pythagoras:

"In fact the said Pythagoras, while busily studying the wisdom of each nation, visited Babylon, and Egypt,
and all Persia, being instructed by the Magi and the priests: and in addition to these he is related to have
studied under the Brahmans (these are Indian philosophers); and from some he gathered astrology, from others geometry,
and arithmetic and music from others, and different things from different nations, and only from the wise men of Greece
did he get nothing, wedded as they were to a poverty and dearth of wisdom: so on the contrary he himself became the author of
instruction to the Greeks in the learning which he had procured from abroad."

Pierre de Fermat (1607–1665) never published his writings; in particular, his work on number theory is contained almost entirely in letters to mathematicians and in private marginal notes.[36] He wrote down nearly no proofs in number theory; he had no models in the area.
One of Fermat's first interests was perfect numbers (which appear in Euclid, Elements IX) and amicable numbers; these topics
led him to work on integer divisors, which were from the beginning among the subjects of the correspondence (1636 onwards)
that put him in
touch with the mathematical community of the day.

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these integers are further restricted to prime numbers, the process is called prime factorization.
When the numbers are sufficiently large, no efficient, non-quantum integer factorization algorithm is known. An effort by several
researchers, concluded in 2009, to factor a 232-digit number (RSA-768) utilizing hundreds of machines took two years and the
researchers estimated that a 1024-bit RSA modulus would take about a thousand times as long.
However, it has not been proven that no efficient algorithm exists. The presumed difficulty of this problem is
at the heart of widely used algorithms in cryptography such as RSA. Many areas of mathematics and computer science
have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing.
Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime numbers. When they are both large, for instance more than two thousand bits long, randomly chosen, and about the same size (but not too close, e.g., to avoid efficient factorization by Fermat's factorization method), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical; that is, as the number of digits of the primes being factored increases, the number of operations required to perform the factorization on any computer increases drastically.
Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem—for example, the RSA problem. An algorithm that efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure.