- Fields of abstract algebra
- >
- Ring theory
- >
- Finite rings
- >
- Modular arithmetic

- Fields of mathematics
- >
- Discrete mathematics
- >
- Number theory
- >
- Modular arithmetic

- Mathematics
- >
- Fields of mathematics
- >
- Arithmetic
- >
- Modular arithmetic

- Mathematics
- >
- Fields of mathematics
- >
- Number theory
- >
- Modular arithmetic

Automorphic number

In mathematics, an automorphic number (sometimes referred to as a circular number) is a natural number in a given number base whose square "ends" in the same digits as the number itself.

Chinese remainder theorem

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of th

Totative

In number theory, a totative of a given positive integer n is an integer k such that 0 < k ≤ n and k is coprime to n. Euler's totient function φ(n) counts the number of totatives of n. The totatives u

Zeller's congruence

Zeller's congruence is an algorithm devised by Christian Zeller in the 19th century to calculate the day of the week for any Julian or Gregorian calendar date. It can be considered to be based on the

Primitive root modulo n

In modular arithmetic, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root modulo n if for every integer a copr

Gauss's lemma (number theory)

Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of

Permuted congruential generator

A permuted congruential generator (PCG) is a pseudorandom number generation algorithm developed in 2014 which applies an output permutation function to improve the statistical properties of a modulo-2

Luhn algorithm

The Luhn algorithm or Luhn formula, also known as the "modulus 10" or "mod 10" algorithm, named after its creator, IBM scientist Hans Peter Luhn, is a simple checksum formula used to validate a variet

Vedic square

In Indian mathematics, a Vedic square is a variation on a typical 9 × 9 multiplication table where the entry in each cell is the digital root of the product of the column and row headings i.e. the rem

Pisano period

In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better know

Quadratic residue

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: Otherwise, q is called a quadratic

Fermat's little theorem

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

Cipolla's algorithm

In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form where , so n is the square of x, and where is an odd prime. Here denotes the finite field with e

Additive polynomial

In mathematics, the additive polynomials are an important topic in classical algebraic number theory.

Proofs of Fermat's little theorem

This article collects together a variety of proofs of Fermat's little theorem, which states that for every prime number p and every integer a (see modular arithmetic).

Discrete logarithm records

Discrete logarithm records are the best results achieved to date in solving the discrete logarithm problem, which is the problem of finding solutions x to the equation given elements g and h of a fini

Jacobi symbol

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is

Kronecker's congruence

In mathematics, Kronecker's congruence, introduced by Kronecker, states that where p is a prime and Φp(x,y) is the modular polynomial of order p, given by for j the elliptic modular function and τ run

Solovay–Strassen primality test

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the te

Euler's criterion

In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely, Let p be an odd prime and a be an integer coprime to p. Then Euler

Luhn mod N algorithm

The Luhn mod N algorithm is an extension to the Luhn algorithm (also known as mod 10 algorithm) that allows it to work with sequences of values in any even-numbered base. This can be useful when a che

Congruence relation

In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in

Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as or , and may also be called

Method of successive substitution

In modular arithmetic, the method of successive substitution is a method of solving problems of simultaneous congruences by using the definition of the congruence equation. It is commonly applied in c

Multiplicative group of integers modulo n

In modular arithmetic, the integers coprime (relatively prime) to n from the set of n non-negative integers form a group under multiplication modulo n, called the multiplicative group of integers modu

Residue number system

A residue numeral system (RNS) is a numeral system representing integers by their values modulo several pairwise coprime integers called the moduli. This representation is allowed by the Chinese remai

Kummer's congruence

In mathematics, Kummer's congruences are some congruences involving Bernoulli numbers, found by Ernst Eduard Kummer. used Kummer's congruences to define the p-adic zeta function.

Table of congruences

In mathematics, a congruence is an equivalence relation on the integers. The following sections list important or interesting prime-related congruences.

Modular exponentiation

Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exc

Congruence of squares

In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms.

Carmichael number

In number theory, a Carmichael number is a composite number , which in modular arithmetic satisfies the congruence relation: for all integers which are relatively prime to . The relation may also be e

Montgomery modular multiplication

In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced

Quadratic reciprocity

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it

Quartic reciprocity

Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x4 ≡ p (mod q) is solvable; the word "reciproc

Tonelli–Shanks algorithm

The Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL algorithm) is used in modular arithmetic to solve for r in a congruence of the form r2 ≡ n (mod p), where p is a prime: that is, to fi

Multiplicative order

In number theory, given a positive integer n and an integer a coprime to n, the multiplicative order of a modulo n is the smallest positive integer k such that . In other words, the multiplicative ord

Legendre symbol

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number p: its value at a (nonzero) quadratic residue mod p is

Linear congruential generator

A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the ol

Combined linear congruential generator

A combined linear congruential generator (CLCG) is a pseudo-random number generator algorithm based on combining two or more linear congruential generators (LCG). A traditional LCG has a period which

Mod n cryptanalysis

In cryptography, mod n cryptanalysis is an attack applicable to block and stream ciphers. It is a form of partitioning cryptanalysis that exploits unevenness in how the cipher operates over equivalenc

Vantieghems theorem

In number theory, Vantieghems theorem is a primality criterion. It states that a natural number n(n≥3) is prime if and only if Similarly, n is prime, if and only if the following congruence for polyno

Kochanski multiplication

Kochanski multiplication is an algorithm that allows modular arithmetic (multiplication or operations based on it, such as exponentiation) to be performed efficiently when the modulus is large (typica

Thue's lemma

In modular arithmetic, Thue's lemma roughly states that every modular integer may be represented by a "modular fraction" such that the numerator and the denominator have absolute values not greater th

Modulo operation

In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the modulus of the operation). Given two positive numbers a a

Discrete logarithm

In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarith

Canon arithmeticus

In mathematics, the Canon arithmeticus is a table of indices and powers with respect to primitive roots for prime powers less than 1000, originally published by Carl Gustav Jacob Jacobi. The tables we

Cubic reciprocity

Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x3 ≡ p (mod q) is solvable; the word "reciprocity" comes from t

Barrett reduction

In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett. A naive way of computing would be to use a fast division algorithm. Barrett reduction is an algori

Wilson's theorem

In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n

Polydivisible number

In mathematics a polydivisible number (or magic number) is a number in a given number base with digits abcde... that has the following properties: 1.
* Its first digit a is not 0. 2.
* The number fo

Kronecker symbol

In number theory, the Kronecker symbol, written as or , is a generalization of the Jacobi symbol to all integers . It was introduced by Leopold Kronecker .

Reduced residue system

In mathematics, a subset R of the integers is called a reduced residue system modulo n if: 1.
* gcd(r, n) = 1 for each r in R, 2.
* R contains φ(n) elements, 3.
* no two elements of R are congruent

Euler's theorem

In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if n and a are coprime positive integers, and is Euler's totient function, then a rai

Fermat primality test

The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.

Verhoeff algorithm

The Verhoeff algorithm is a checksum formula for error detection developed by the Dutch mathematician Jacobus Verhoeff and was first published in 1969. It was the first decimal check digit algorithm w

Carmichael function

In number theory, a branch of mathematics, the Carmichael function λ(n) of a positive integer n is the smallest positive integer m such that holds for every integer a coprime to n. In algebraic terms,

Hensel's lemma

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a pri

Jordan's totient function

Let be a positive integer. In number theory, the Jordan's totient function of a positive integer equals the number of -tuples of positive integers that are less than or equal to and that together with

Root of unity modulo n

In mathematics, namely ring theory, a kth root of unity modulo n for positive integers k, n ≥ 2, is a root of unity in the ring of integers modulo n, that is, a solution x to the equation (or congruen

Pocklington's algorithm

Pocklington's algorithm is a technique for solving a congruence of the form where x and a are integers and a is a quadratic residue. The algorithm is one of the first efficient methods to solve such a

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was

Modular multiplicative inverse

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In th

Lehmer random number generator

The Lehmer random number generator (named after D. H. Lehmer), sometimes also referred to as the Park–Miller random number generator (after Stephen K. Park and Keith W. Miller), is a type of linear co

© 2023 Useful Links.