 # Congruences

## Congruences Topics

Sort by:

### Multiplicative order

Let be a positive number having primitive roots. If is a primitive root of , then the numbers 1, , , ..., form a reduced residue system modulo , where is the totient function. In this set, there are primitive roots, and these are the numbers , where is relatively prime to .The smallest exponent for which , where and are given numbers, is called the multiplicative order (or sometimes haupt-exponent or modulo order) of (mod ).The multiplicative order is implemented in the Wolfram Language as MultiplicativeOrder[g, n].The number of bases having multiplicative order is , where is the totient function. Cunningham (1922) published the multiplicative order for primes to 25409 and bases 2, 3, 5, 6, 7, 10, 11, and 12.Multiplicative orders exist for that are relatively prime to . For example, the multiplicative order of 10 (mod 7) is 6, since(1)The multiplicative order of 10 mod an integer relatively prime to 10 gives the period of the decimal expansion of the..

### Wolstenholme's theorem

If is a prime , then the numerator of the harmonic number(1)is divisible by and the numerator of the generalized harmonic number(2)is divisible by . The numerators of are sometimes known as Wolstenholme numbers.These imply that if is prime, then(3)

### Congruence equation

An equation of the form(1)where the values of for which the equation holds are sought. Such an equation may have none, one, or many solutions. There is a general method for solving both the general linear congruence equation(2)and the general quadratic congruenceequation(3)However, solution of the general polynomial congruence(4)is intractable. Note that any polynomial congruence will give congruent results when congruent values are substituted.

### Thue's theorem

If , (i.e., and are relatively prime), and is the least integer , then there exist an and such thatwhere and (Nagell 1951, pp. 122-124; Shanks 1993, p. 161)

### Modular inverse

A modular inverse of an integer (modulo ) is the integer such thatA modular inverse can be computed in the Wolfram Language using PowerMod[b, -1, m].Every nonzero integer has an inverse (modulo ) for a prime and not a multiple of . For example, the modular inverses of 1, 2, 3, and 4 (mod 5) are 1, 3, 2, and 4.If is not prime, then not every nonzero integer has a modular inverse. In fact, a nonzero integer has a modular inverse modulo iff and are relatively prime. For example, (mod 4) and (mod 4), but 2 does not have a modular inverse.The triangle above (OEIS A102057) gives modular inverses of (mod ) for , 2, ..., and , 3, .... 0 indicates that no modular inverse exists.If and are relatively prime, there exist integers and such that , and such integers may be found using the Euclidean algorithm. Considering this equation modulo , it follows that ; i.e., .If and are relatively prime, then Euler's totient theorem states that , where is the totient function. Hence, ...

### Successive square method

The successive square method is an algorithm to compute in a finite field . The first step is to decompose in successive powers of two,(1)where , which gives in base 2. can then be represented as(2)(3)This term can be computed by successive steps as(4)(5)(6)(7)For example, to compute in the finite field , first decompose into , then follow the above steps: (8)(9)(10)(11)(12)From there, the final answer can be computed as(13)The successive square method is implemented in the Wolfram Language as PowerMod[a, b, n].

### Modular arithmetic

Modular arithmetic is the arithmetic of congruences, sometimes known informally as "clock arithmetic." In modular arithmetic, numbers "wrap around" upon reaching a given fixed quantity, which is known as the modulus (which would be 12 in the case of hours on a clock, or 60 in the case of minutes or seconds on a clock).Formally, modular arithmetic is the arithmetic of any nontrivial homomorphic image of the ring of integers. For any such homomorphic image of , there is an integer such that is isomorphic to the ring of integers modulo . The addition in the ring is determined from addition in by computing the remainder, upon division by , of the sum of two integers and . Similarly, for multiplication in the ring , one multiplies two integers and , and computes the remainder upon division of by .For each positive integer , the ring has elements, namely the equivalence classes of each of the nonnegative integers less than , under the equivalence..

### Minimal residue

The minimal residue of is the value or , whichever is smaller in absolute value, where . If (so that ), then the minimal residue is taken as . The table below illustrates the common (positive) and minimal residues for 0, 1, 2, and 3 (mod 4).common residue minimal residue 0001112233The minimal residue is implemented in the Wolfram Language as Mod[a, m, -m/2].

### Linear congruence equation

A linear congruence equation(1)is solvable iff the congruence(2)with is the greatest common divisor is solvable. Let one solution to the original equation be . Then the solutions are , , , ..., . If , then there is only one solution .The solution of a linear congruence can be found in the Wolfram Language using Reduce[a*x == b, x, Modulus -> m].Solution to a linear congruence equation is equivalent to finding the value of a fractional congruence, for which a greedy-type algorithm exists. In particular, (1) can be rewritten as(3)which can also be written(4)In this form, the solution can be found as Mod[b y, m] of the solution returned by the Wolfram Language function PowerMod[a, , m]. This is known as a modular inverse.Two or more simultaneous linear congruences(5)(6)are solvable using the Chinese remaindertheorem...

### Chinese remainder theorem

Let and be positive integers which are relatively prime and let and be any two integers. Then there is an integer such that(1)and(2)Moreover, is uniquely determined modulo . An equivalent statement is that if , then every pair of residue classes modulo and corresponds to a simple residue class modulo .The Chinese remainder theorem is implemented in the Wolfram Language as ChineseRemainder[a1, a2, ...m1, m2, ...]. The Chinese remainder theorem is also implemented indirectly using Reduce in with a domain specification of Integers.The theorem can also be generalized as follows. Given a set of simultaneous congruences(3)for , ..., and for which the are pairwise relatively prime, the solution of the set of congruences is(4)where(5)and the are determined from(6)

### Residue class

The residue classes of a function mod are all possible values of the residue . For example, the residue classes of (mod 6) are , sinceare all the possible residues.A complete residue system is a set of integers containing one element from each class, so would be a complete residue system for (mod 6).The residue classes prime to form a group under the binary multiplication operation (mod ), where is the totient function (Shanks 1993) and the group is classed a modulo multiplication group.

### Chinese hypothesis

The hypothesis that an integer is prime iff it satisfies the condition that is divisible by . Dickson (2005, p. 91) stated that Leibniz believe to have proved that this congruence implies that is prime. In actuality, this condition is necessary but not sufficient for to be prime since, for example, is divisible by 341, but is composite.Composite numbers (such as 341) for which is divisible by are called Poulet numbers, and are a special class of Fermat pseudoprimes. The Chinese hypothesis is a special case of Fermat's little theorem.The "Chinese hypothesis," "Chinese congruence," or "Chinese theorem," as it is sometimes called, is commonly attributed to Chinese scholars more than 2500 years ago. However, this oft-quoted attribution (e.g., Honsberger 1973, p. 3) is a myth originating with Jeans (1897-98), who wrote that "a paper found among those of the late Sir Thomas Wade and dating from..

### Residue

The word residue is used in a number of different contexts in mathematics. Two of the most common uses are the complex residue of a pole, and the remainder of a congruence.The number in the congruence is called the residue of (mod ). The residue of large numbers can be computed quickly using congruences. For example, to find (mod 17), note that(1)(2)(3)(4)so(5)

### Functional congruence

A congruence of the formwhere and are both integer polynomials. Functional congruences are sometimes also called "identical congruences" (Nagell 1951, p. 74).

### Reduced residue system

Any system of integers, where is the totient function, representing all the residue classes relatively prime to is called a reduced residue system (Nagell 1951, p. 71).

A congruence of the form(1)where , , and are integers. A general quadratic congruence can be reduced to the congruence(2)and can be solved using excludents, although solutionof the general polynomial congruence(3)is intractable.

### Fermat's little theorem converse

The converse of Fermat's little theorem is also known as Lehmer's theorem. It states that, if an integer is prime to and and there is no integer for which , then is not prime. Here, is called a witness to the primality of . This theorem is the basis for the Pratt primality certificate.

### Cancellation law

If and (i.e., and are relatively prime), then .

### Excludent

A method which can be used to solve any quadraticcongruence equation. This technique relies on the fact that solvingis equivalent to finding a value such thatPick a few small moduli . If mod does not make a quadratic residue of , then this value of may be excluded. Furthermore, values of are never necessary.

### Blankinship algorithm

A method for finding solutions and to a linear congruenceby constructing a matrix formed by adjoining a vector containing and with a unit matrix,and applying the Euclidean algorithm to the first column, while extending the operations to all rows. The algorithm terminates when the first column contains the greatest common divisor .

### Exact covering system

A system of congruences mod with is called a complete residue system (or covering system) if every integer satisfies for at least one value of . A covering system in which each integer is covered by just one congruence is called an exact covering system.

### Bauer's theorem

Let be an integer and letbe an integer polynomial that has at least one real root. Then has infinitely many prime divisors that are not congruent to 1 (mod ) (Nagell 1951, p. 168).

### Bauer's identical congruence

Let denote the set of the numbers less than and relatively prime to , where is the totient function. Define(1)Then a theorem of Lagrange states that(2)for an odd prime (Hardy and Wright 1979, p. 98). Actually, this relationship holds for some composite values as well. Value for which it holds are , 3, 4, 5, 6, 7, 10, 11, 13, 17, 19, 23, 29, ... (OEIS A158008).This can be generalized as follows. Let be an odd prime divisor of and the highest power which divides , then(3)and, in particular,(4)Now, if is even and is the highest power of 2 that divides , then(5)and, in particular,(6)

### Newman's conjecture

If is an integer, then for every residue class (mod ), there are infinitely many nonnegative integers for which , where is the partition function P.

### Artin's constant

Let be a positive nonsquare integer. Then Artin conjectured that the set of all primes for which is a primitive root is infinite. Under the assumption of the generalized Riemann hypothesis, Artin's conjecture was solved by Hooley (1967; Finch 2003, p. 105).Let be not an th power for any such the squarefree part of satisfies (mod 4). Let be the set of all primes for which such an is a primitive root. Then Artin also conjectured that the density of relative to the primes is given independently of the choice of by , where(1)(OEIS A005596), and is the th prime.The significance of Artin's constant is more easily seen by describing it as the fraction of primes for which has a maximal period repeating decimal, i.e., is a full reptend prime (Conway and Guy 1996) corresponding to a cyclic number. is connected with the prime zeta function by(2)where is a Lucas number (Ribenboim 1998, Gourdon and Sebah). Wrench (1961) gave 45 digits of , and Gourdon and Sebah..

### Discrete logarithm

If is an arbitrary integer relatively prime to and is a primitive root of , then there exists among the numbers 0, 1, 2, ..., , where is the totient function, exactly one number such thatThe number is then called the discrete logarithm of with respect to the base modulo and is denotedThe term "discrete logarithm" is most commonly used in cryptography, although the term "generalized multiplicative order" is sometimes used as well (Schneier 1996, p. 501). In number theory, the term "index" is generally used instead (Gauss 1801; Nagell 1951, p. 112).For example, the number 7 is a positive primitive root of (in fact, the set of primitive roots of 41 is given by 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35), and since , the number 15 has multiplicative order 3 with respect to base 7 (modulo 41) (Nagell 1951, p. 112). The generalized multiplicative order is implemented in the Wolfram Language..

### Artin's conjecture

There are at least two statements which go by the name of Artin's conjecture.If is any complex finite-dimensional representation of the absolute Galois group of a number field, then Artin showed how to associate an -series with it. These -series directly generalize zeta functions and Dirichlet -series, and as a result of work by Richard Brauer, is known to extend to a meromorphic function on the complex plane. Artin's conjecture predicts that it is in fact holomorphic, i.e., has no poles, with the possible exception of a pole at (Artin 1923/1924). Compare with the generalized Riemann hypothesis, which deals with the locations of the zeros of certain -series.The second conjecture states that every integer not equal to or a square number is a primitive root modulo for infinitely many and proposes a density for the set of such which are always rational multiples of a constant known as Artin's constant. There is an analogous theorem for functions instead..

### Primitive root

A primitive root of a prime is an integer such that (mod ) has multiplicative order (Ribenboim 1996, p. 22). More generally, if ( and are relatively prime) and is of multiplicative order modulo where is the totient function, then is a primitive root of (Burton 1989, p. 187). The first definition is a special case of the second since for a prime.A primitive root of a number (but not necessarily the smallest primitive root for composite ) can be computed in the Wolfram Language using PrimitiveRoot[n].If has a primitive root, then it has exactly of them (Burton 1989, p. 188), which means that if is a prime number, then there are exactly incongruent primitive roots of (Burton 1989). For , 2, ..., the first few values of are 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 2, 4, 2, 4, 4, 8, ... (OEIS A010554). has a primitive root if it is of the form 2, 4, , or , where is an odd prime and (Burton 1989, p. 204). The first few for which primitive roots exist are 2, 3, 4,..

### Congruence

If two numbers and have the property that their difference is integrally divisible by a number (i.e., is an integer), then and are said to be "congruent modulo ." The number is called the modulus, and the statement " is congruent to (modulo )" is written mathematically as(1)If is not integrally divisible by , then it is said that " is not congruent to (modulo )," which is written(2)The explicit "(mod )" is sometimes omitted when the modulus is understood by context, so in such cases, care must be taken not to confuse the symbol with the equivalence sign.The quantity is sometimes called the "base," and the quantity is called the residue or remainder. There are several types of residues. The common residue defined to be nonnegative and smaller than , while the minimal residue is or , whichever is smaller in absolute value.Congruence arithmetic is perhaps most familiar as a generalization of the..

### Suborder function

The multiplicative suborder of a number (mod ) is the least exponent such that (mod ), or zero if no such exists. An always exists if and .This function is denoted and can be implemented in the Wolfram Language as: Suborder[a_,n_] := If[n>1&& GCD[a,n] == 1, Min[MultiplicativeOrder[a, n, {-1, 1}]], 0 ]The following table summarizes for small values of and .OEIS for , 1, ...20, 0, 0, 1, 0, 2, 0, 3, 0, 3, 0, 5, 0, 6, 0, ...3A1034890, 0, 1, 0, 1, 2, 0, 3, 2, 0, 2, 5, 0, 3, 3, ...40, 0, 0, 1, 0, 1, 0, 3, 0, 3, 0, 5, 0, 3, 0, ...5A1034910, 0, 1, 1, 1, 0, 1, 3, 2, 3, 0, 5, 2, 2, 3, ...

### Congruent

There are at least two meanings on the word congruent in mathematics. Two geometric figures are said to be congruent if one can be transformed into the other by an isometry (Coxeter and Greitzer 1967, p. 80). This relationship, called geometric congruence, is written . (Unfortunately, the symbol is also used to denote an isomorphism.)A number is said to be congruent to modulo if ( divides ).