List of number theory topics

Last updated

This is a list of number theory topics, by Wikipedia page. See also:

Contents

Divisibility

Fractions

Modular arithmetic

Arithmetic functions

Analytic number theory: additive problems

Algebraic number theory

See list of algebraic number theory topics

Quadratic forms

L-functions

Diophantine equations

Diophantine approximation

Sieve methods

Named primes

Combinatorial number theory

Computational number theory

Note: Computational number theory is also known as algorithmic number theory.

Primality tests

Integer factorization

Pseudo-random numbers

see also List of random number generators.

Arithmetic dynamics

History

Related Research Articles

In number theory, a Carmichael number is a composite number which satisfies the modular arithmetic congruence relation:

In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form Mn = 2n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If n is a composite number then so is 2n − 1. Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form Mp = 2p − 1 for some prime p.

Prime number Positive integer with exactly two divisors, 1 and itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.

Fermat's little theorem states that if p is a prime number, then for any integer a, the number apa is an integer multiple of p. In the notation of modular arithmetic, this is expressed as

In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. Sophie Germain primes and safe primes have applications in public key cryptography and primality testing. It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven.

In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form

Algebraic number theory Branch of number theory

Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic objects such as algebraic number fields and their rings of integers, finite fields, and function fields. These properties, such as whether a ring admits unique factorization, the behavior of ideals, and the Galois groups of fields, can resolve questions of primary importance in number theory, like the existence of solutions to Diophantine equations.

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:

In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and

In number theory, a Wieferich prime is a prime number p such that p2 divides 2p − 1 − 1, therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides 2p − 1 − 1. Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's last theorem, at which time both of Fermat's theorems were already well known to mathematicians.

John Lewis Selfridge, was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.

A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes".

The Erdős–Straus conjecture states that every fraction 4/n equals a sum of three positive unit fractions 1/x + 1/y + 1/z. The question of whether this is always possible belongs to the mathematical field of number theory and can be expressed as a Diophantine equation. It is named after Paul Erdős and Ernst G. Straus, who formulated the conjecture in 1948, and is one of many conjectures by Erdős. More generally, expressions of fractions as sums of unit fractions are known as Egyptian fractions, because of their use in ancient Egyptian mathematics.

The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff.

A timeline of number theory.

This is a timeline of pure and applied mathematics history. It is divided here into three stages, corresponding to stages in the development of mathematical notation: a "rhetorical" stage in which calculations are described purely by words, a "syncopated" stage in which quantities and common algebraic operations are beginning to be represented by symbolic abbreviations, and finally a "symbolic" stage, in which comprehensive notational systems for formulas are the norm.