Draft:Elementary number theory

originally forked from the elementary number theory section in the number theory article

Elementary number theory deals with the topics in number theory by means of basic methods in arithmetic. Its primary subjects of study are divisibility, factorization, and primality, as well as congruences in modular arithmetic. Other topic in elementary number theory are Diophantine equations, continued fraction, integer partitions, and Diophantine approximations.

Definition

More specifically, elementary number theory works with elementary proofs, a term that excludes the use of complex numbers but may include basic analysis. For example, the prime number theorem was first proven using complex analysis in 1896, but an elementary proof was found only in 1949 by Erdős and Selberg. The term is somewhat ambiguous. For example, proofs based on complex Tauberian theorems, such as Wiener–Ikehara, are often seen as quite enlightening but not elementary despite using Fourier analysis, not complex analysis. Here as elsewhere, an elementary proof may be longer and more difficult for most readers than a more advanced proof.

Arithmetic is the study of numerical operations and investigates how numbers are combined and transformed using the arithmetic operations of addition, subtraction, multiplication, division, exponentiation, extraction of roots, and logarithms. Multiplication, for instance, is an operation that combines two numbers, referred to as factors, to form a single number, termed the product, such as $2\times 3=6$.

Number theory has the reputation of being a field many of whose results can be stated to the layperson. At the same time, many of the proofs of these results are not particularly accessible, in part because the range of tools they use is, if anything, unusually broad within mathematics.

Divisibility, primality, factorisation

Divisibility is a property between two nonzero integers related to division. Euclid's division lemma states that any integer $a$ and positive integer divisor $b$ can be written as $a=bq+r$, where the remainder $r<b$ accounts for the left over quantity. The number $a$ is said to be divisible by $b$ if $a$ is divided evenly by $b$ without remainder; that is, if $r=0$. An equivalent formulation is that $b$ divides $a$ and is denoted by a vertical bar, which in this case is $b|a$. Elementary number theory studies divisibility rules in order to quickly identify if a given integer is divisible by a fixed divisor. For instance, it is known that any integer is divisible by 3 if its digit sum is divisible by 3. Elementary number theory studies the divisibility properties of integers such as parity (even and odd numbers), prime numbers, and perfect numbers. A prime number is an integer greater than 1 whose only positive divisors are 1 and the prime itself. A positive integer greater than 1 that is not prime is called a composite number. There are infinitely many prime numbers, as demonstrated by Euclid's theorem.

Factorization is a method of expressing a number as a product. Specifically in number theory, integer factorization is the decomposition of an integer into a product of integers. The unique factorization theorem is the fundamental theorem of arithmetic that relates to prime factorization, integer factorization into a product of prime numbers. The theorem states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. For example, $120$ is expressed uniquely as $2\times 2\times 2\times 3\times 5$ or simply $2^{3}\times 3\times 5$.

Modular arithmetic

Modular arithmetic works with finite sets of integers and introduces the concepts of congruence and residue classes. A congruence of two integers $a,b$ modulo $n$ is an equivalence relation whereby $n|(a-b)$ is true. This written as $a\equiv b{\pmod {n}}$, where $a$ is said to be congruent to $b$ modulo $n$. Performing Euclidean division on both $a$ and $n$, and on $b$ and $n$, yields the same remainder. A residue class modulo $n$ is a set that contains all integers congruent to a specified $r$ modulo $n$. For example, $6\mathbb {Z} +1$ contains all multiples of 6 incremented by 1. An influential theorem is Fermat's little theorem, which states that if $p$ is prime, then for any integer $a$, the equation $a^{p}\equiv a{\pmod {p}}$ is true. Equivalently, if $a$ is coprime to $p$, then$$a^{p-1}\equiv 1{\pmod {p}}.$$