The Jacobi symbol

The Jacobi symbol is a generalization of the Legendre symbol. In this post, we define the Jacobi symbol and discuss some of its important properties. The Legendre symbol (coupled with the law of reciprocity) is a useful tool in determining whether a number is a quadratic residue modulo an odd prime. However, the Legendre symbol is also restrictive since the bottom argument must be a prime. The Jacobi symbol generalizes the Legendre symbol and in many cases is easier to evaluate than the Legendre symbol. This is demonstrated in several examples.

____________________________________________________________________________

Defining The Jacobi Symbol

The Legendre symbol is $\displaystyle \biggl(\frac{a}{p}\biggr)$ where the bottom argument is always an odd prime and the top argument can be any integer. When $a$ is an integer that is relatively prime to the odd prime $p$, the Legendre symbol $\displaystyle \biggl(\frac{a}{p}\biggr)$ carries information on whether the integer $a$ is quadratic residue modulo $p$. The following gives the definition of the Legendre symbol.

$\displaystyle \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl} 0 &\ \text{if } a \equiv 0 \ (\text{mod} \ p) \\ 1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a \text{ is a quadratic residue modulo }p\\ -1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a \text{ is a quadratic nonresidue modulo }p \end{array} \right.$

The Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ has the same look as the Legendre symbol. The top argument can be any integer. The bottom argument is an odd positive integer. If the odd positive integer $n>1$ has the prime factorization $n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_t^{e_t}$, the Jacobi symbol is defined as follows:

$\displaystyle \biggl(\frac{a}{n}\biggr)=\biggl(\frac{a}{p_1}\biggr)^{e_1} \times \biggl(\frac{a}{p_2}\biggr)^{e_2} \times \cdots \times \biggl(\frac{a}{p_t}\biggr)^{e_t}$

For convenience, we define $\displaystyle \biggl(\frac{a}{1}\biggr)=1$. A slightly different, but equivalent, definition is that whenever the odd integer $n>1$ has the prime factorization $n=q_1 \times q_2 \times \cdots \times q_k$ (the prime numbers $q_j$ are not necessarily distinct), the symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ is defined as follows:

$\displaystyle \biggl(\frac{a}{n}\biggr)=\biggl(\frac{a}{q_1}\biggr) \times \biggl(\frac{a}{q_2}\biggr) \times \cdots \times \biggl(\frac{a}{q_k}\biggr)$

The Jacobi symbol is defined using the Legendre symbol according to the prime factorization of the bottom argument.

____________________________________________________________________________

Properties of The Jacobi Symbol

Now that the Jacobi symbol has been defined based on the Legendre symbol, there are two natural questions.

• Does the value of $\displaystyle \biggl(\frac{a}{n}\biggr)= \pm 1$ indicates that $a$ is a quadratic residue or nonresidue modulo $n$?
• The Legendre symbol follows a set of rules (e.g. the law of quadratic reciprocity) that make the Legendre symbol a versatile tool. Does the Jacobi symbol follow these rules? Conceptually, evaluating the Jacobi symbol requires factoring the bottom argument of the symbol. On the surface, this appears to be a limitation. However, if the Jacobi symbol follows the rules for the Legendre symbol including the law of quadratic reciprocity, it will be just as easy to evaluate the Jacobi symbol.

For the first question, the following is true: If $a$ is a quadratic residue modulo $n$, then $\displaystyle \biggl(\frac{a}{n}\biggr)=1$. The contrapositive of this statement is that if $\displaystyle \biggl(\frac{a}{n}\biggr)=-1$, then the number $a$ is a quadratic nonresidue modulo the odd integer $n$, i.e. the equation $x^2 \equiv a \ (\text{mod} \ n)$ has no solutions. However, the value of $\displaystyle \biggl(\frac{a}{n}\biggr)=1$ does not imply that $a$ is a quadratic residue modulo $n$. For example, $\displaystyle \biggl(\frac{2}{15}\biggr)=1$ but the equation $x^2 \equiv 2 \ (\text{mod} \ 15)$ has no solutions. Note that both equations $x^2 \equiv 2 \ (\text{mod} \ 3)$ and $x^2 \equiv 2 \ (\text{mod} \ 5)$ have no solutions. This means that the value of $\displaystyle \biggl(\frac{2}{15}\biggr)=1$ is the product of two Legendre symbols of -1.

Theorem 1
Let $n$ be an odd positive integer. Let $a$ be such that $\text{GCD}(a,n)=1$. Then If $a$ is a quadratic residue modulo $n$, then $\displaystyle \biggl(\frac{a}{n}\biggr)=1$. The converse does not hold if $n$ is not a prime.

Proof
Suppose that $a$ is a quadratic residue modulo $n$, i.e. the equation $x^2 \equiv a \ (\text{mod} \ n)$ has a solution. Let $n=p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_t^{e_t}$ be the prime factorization of $n$. Let $m_i=p_i^{e_i}$ for each $i$. By the Chinese remainder theorem, the equation $x^2 \equiv a \ (\text{mod} \ m_i)$ has a solution for each $i=1,2,\cdots,t$. it then follows that the equation $x^2 \equiv a \ (\text{mod} \ p_i)$ has a solution too for each $i=1,2,\cdots,t$. Hence the Legendre symbol $\displaystyle \biggl(\frac{a}{p_i}\biggr)=1$ for each $i$. It follows that the Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)=1$. $\square$

For the second question, the rules that are obeyed by the Legendre symbol are also obeyed by the Jacobi symbol. Some of the rules are easily seen to carry over to the Jacobi symbol. The fact that the law of quadratic reciprocity and the two supplements are obeyed by the Jacobi symbol is not entirely obvious from the definition. However the proof is not difficult. We give a complete proof here.

Lemma 2
Let $a$ and $b$ be odd positive integers. The following two conditions hold.

$\displaystyle \frac{a-1}{2} \times \frac{b-1}{2} \equiv \frac{ab-1}{2} \ (\text{mod} \ 2)$

$\displaystyle \frac{a^2-1}{8} \times \frac{b^2-1}{8} \equiv \frac{(ab)^2-1}{8} \ (\text{mod} \ 2)$

Proof
The lemma is established by the following derivation:

$\displaystyle \frac{ab-1}{2}-\biggl[\frac{a-1}{2}+\frac{b-1}{2} \biggr]=\frac{ab-a-b+1}{2}=\frac{(a-1)(b-1)}{2}$

$\displaystyle \frac{(ab)^2-1}{8}-\biggl[\frac{a^2-1}{8}+\frac{b^2-1}{8} \biggr]=\frac{(ab)^2-a^2-b^2+1}{8}=\frac{(a^2-1)(b^2-1)}{8}$

Because both $a$ and $b$ are odd integers, the right-hand-side of both equations are even integers and thus $\equiv 0 \ (\text{mod} \ 2)$. $\square$

Theorem 3 (Properties of Jacobi Symbol)

1. $\displaystyle \biggl(\frac{a}{n}\biggr) = \left\{ \begin{array}{rl} 0 &\ \text{if } \text{GCD}(a,n) >1 \\ \pm 1 &\ \text{if } \text{GCD}(a,n)=1 \end{array} \right.$
2. $\text{ }$

3. If $n$ is a prime, then the Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ coincides with the Legendre symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$.
4. $\text{ }$

5. If $a \equiv b \ (\text{mod} \ n)$, then $\displaystyle \biggl(\frac{a}{n}\biggr)=\biggl(\frac{b}{n}\biggr)$.
6. $\text{ }$

7. The Jacobi symbol is multiplicative when the bottom argument is fixed, i.e. $\displaystyle \biggl(\frac{ab}{n}\biggr)=\biggl(\frac{a}{n}\biggr) \biggl(\frac{b}{n}\biggr)$.
8. $\text{ }$

9. The Jacobi symbol is multiplicative when the upper argument is fixed, i.e. $\displaystyle \biggl(\frac{a}{mn}\biggr)=\biggl(\frac{a}{m}\biggr) \biggl(\frac{a}{n}\biggr)$.
10. $\text{ }$

11. (The law of quadratic reciprocity)
Let $a$ and $b$ be relatively prime odd positive integers. Then

$\displaystyle \biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)=(-1)^{(a-1)/2 \times (b-1)/2}$

Equivalently, $\displaystyle \biggl(\frac{a}{b}\biggr) = \left\{ \begin{array}{rl} \displaystyle \biggl(\frac{b}{a}\biggr) &\ \text{if } a \equiv 1 \ (\text{mod} \ 4) \text{ or } b \equiv 1 \ (\text{mod} \ 4) \\ \displaystyle -\biggl(\frac{b}{a}\biggr) &\ \text{if } a \equiv b \equiv 3 \ (\text{mod} \ 4) \end{array} \right.$

12. (First supplement to the law of quadratic reciprocity)
Let $n$ be an odd positive integer. Then

$\displaystyle \biggl(\frac{-1}{n}\biggr)=(-1)^{(n-1)/2}$.

Equivalently, $\displaystyle \biggl(\frac{-1}{n}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } n \equiv 1 \ (\text{mod} \ 4) \\ -1 &\ \text{if } n \equiv 3 \ (\text{mod} \ 4) \end{array} \right.$

13. (Second supplement to the law of quadratic reciprocity)
Let $n$ be an odd positive integer. Then

$\displaystyle \biggl(\frac{2}{n}\biggr)=(-1)^{(n^2-1)/8}$.

Equivalently, $\displaystyle \biggl(\frac{2}{n}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } n \equiv 1 \ (\text{mod} \ 8) \text{ or } n \equiv 7 \ (\text{mod} \ 8) \\ -1 &\ \text{if } n \equiv 3 \ (\text{mod} \ 8) \text{ or } n \equiv 5 \ (\text{mod} \ 8) \end{array} \right.$

Proof
For the first bullet point, if the top argument and the bottom argument have a prime factor in common, then one of the Legendre symbols that make up the Jacobi symbol is zero. If the top argument and the bottom argument have no prime factor in common, then all the Legendre symbols that make up the Jacobi symbol is either 1 or -1.

The second point is clear. If the bottom argument is an odd prime, the definition of Jacobi symbol leads to the Legendre symbol.

For bullet points 3, 4 and 5, simply write out the Jacobi symbol and then use the corresponding properties of the Legendre symbol.

Now the proof of bullet point 6 (the law of quadratic reciprocity). Let $a$ and $b$ be relatively prime. Let $a=p_1 \times p_2 \times \cdots \times p_w$ and $b=q_1 \times q_2 \times \cdots \times q_t$ be their prime factorizations. Note that the primes $p_i$ are not necessarily distinct and the primes $q_i$ are not necessarily distinct. However, $p_i \ne q_j$ since $a$ and $b$ are relatively prime. Consider the following derivation of the product $\displaystyle \biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)$.

\displaystyle \begin{aligned}\biggl(\frac{a}{b}\biggr) \biggl(\frac{b}{a}\biggr)&=\prod \limits_{i=1}^t \biggl(\frac{a}{q_i}\biggr) \ \prod \limits_{j=1}^w \biggl(\frac{b}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \ \prod \limits_{j=1}^w \prod \limits_{i=1}^t \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \ \prod \limits_{i=1}^t \prod \limits_{j=1}^w \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w\biggl(\frac{p_j}{q_i}\biggr) \biggl(\frac{q_i}{p_j}\biggr) \\&=\prod \limits_{i=1}^t \prod \limits_{j=1}^w (-1)^{(p_j-1)/2 \times (q_i-1)/2} \\&=(-1)^E \end{aligned}

where

$\displaystyle E=\sum \limits_{i,j} \biggl[\frac{p_j-1}{2} \times \frac{q_i-1}{2} \biggr]$

The bullet point 6 is established after the quantity $E$ is simplified as follows:

\displaystyle \begin{aligned} \sum \limits_{i,j} \biggl[\frac{p_j-1}{2} \times \frac{q_i-1}{2} \biggr]&=\sum_j \biggl[\sum_i \frac{q_i-1}{2}\biggr] \frac{p_j-1}{2} \\&\equiv \sum_j \biggl[ \frac{b-1}{2}\biggr] \frac{p_j-1}{2} \ \ \ \text{ Use Lemma 2}\\&\equiv \frac{b-1}{2} \sum_j \frac{p_j-1}{2} \\&\equiv \frac{b-1}{2} \frac{a-1}{2} \ (\text{mod} \ 2) \ \ \ \text{ Use Lemma 2} \end{aligned}

Now consider the bullet point #7 (the first supplement to the law of quadratic reciprocity). The proof is an induction proof on the number of prime factors of $n$. If $n$ is a prime, then it is done. So we assume $n=p_1 \times p_2$ (not necessarily distinct). Consider the following derivation:

\displaystyle \begin{aligned} \biggl(\frac{-1}{n}\biggr)&=\biggl(\frac{-1}{p_1}\biggr) \biggl(\frac{-1}{p_2}\biggr) \\&=(-1)^{(p_1-1)/2} \ (-1)^{(p_2-1)/2} \\&=(-1)^{(p_1-1)/2+(p_2-1)/2} \\&\equiv (-1)^{(p_1 \times p_2 -1)/2} \ \ \ \ \ \text{Use Lemma 2} \\&\equiv (-1)^{(n -1)/2} \ (\text{mod} \ 2) \end{aligned}

It is a straightforward argument that whenever the property is true for $n$ being a product of $k$ primes, the property is true for $n$ being a product of $k+1$ primes. Thus bullet 7 is established.

The proof of bullet point 8 (the second supplement to the law of quadratic reciprocity) is also an induction proof on the number of prime factors of $n$. The most important case is the of two prime factors.

\displaystyle \begin{aligned} \biggl(\frac{2}{n}\biggr)&=\biggl(\frac{2}{p_1}\biggr) \biggl(\frac{2}{p_2}\biggr) \\&=(-1)^{(p_1^2-1)/8} \ (-1)^{(p_2^2-1)/8} \\&=(-1)^{(p_1^2-1)/8+(p_2^2-1)/8} \\&\equiv (-1)^{((p_1 \times p_2)^2 -1)/8} \ \ \ \ \ \text{Use Lemma 2} \\&\equiv (-1)^{(n^2 -1)/8} \ (\text{mod} \ 2) \end{aligned}

With the 2-case established, it is straightforward to carry out the remainder of the induction proof of bullet 8. $\square$

____________________________________________________________________________

Examples

Example 1
Evaluate $\displaystyle \biggl(\frac{1783}{7523}\biggr)$, an example where both the upper and lower arguments are primes. In the previous post, the example is calculated using only Legendre symbol. Here we work it in Jacobi symbol. As much as possible, we flip the symbol without factoring.

\displaystyle \begin{aligned} \biggl(\frac{1783}{7523}\biggr)&=-\biggl(\frac{7523}{1783}\biggr) \\&=-\biggl(\frac{391}{1783}\biggr) \ \ *\\&=\biggl(\frac{1783}{391}\biggr) \\&=\biggl(\frac{219}{391}\biggr) \ \ *\\&=-\biggl(\frac{391}{219}\biggr) \\&=-\biggl(\frac{172}{219}\biggr) \\&=-\biggl(\frac{2}{219}\biggr)^2 \biggl(\frac{43}{219}\biggr) \\&=-\biggl(-1\biggr)^2 (-1) \biggl(\frac{219}{43}\biggr) \\&=\biggl(\frac{4}{43}\biggr) \\&=1 \end{aligned}

One advantage of using Jacobi symbol is that when the upper argument is an odd integer that is not prime, we can still flip it (the steps with *). Then reduce and then flip again until we reach a point with small numbers. Thinking in Legendre symbol only, the steps with * cannot be flipped. As Jacobi symbols, they can be flipped freely as long as the arguments are odd integers. The advantage may not be apparent in this example. When the composite integers are large to the point that their factorizations are in effect not obtainable, this advantage is huge. $\square$

Example 2
Evaluate $\displaystyle \biggl(\frac{a}{p}\biggr)$ where $p=$ 1298351, an odd prime and $a=$ 756479. This is Example 2 in this previous post. The number $a$ is not a prime. Here we use Jacobi symbol to demonstrate that factoring is not needed. We can start by flipping. We have the following derivation.

\displaystyle \begin{aligned} \biggl(\frac{756479}{1298351}\biggr)&=-\biggl(\frac{1298351}{756479}\biggr) \\&=-\biggl(\frac{541872}{756479}\biggr) \\&=-\biggl(\frac{2}{756479}\biggr)^4 \times \biggl(\frac{33867}{756479}\biggr) \\&=-\biggl(1\biggr)^4 \times (-1) \biggl(\frac{756479}{33867}\biggr) \\&=\biggl(\frac{11405}{33867}\biggr) \\&=\biggl(\frac{33867}{11405}\biggr) \\&=\biggl(\frac{11057}{11405}\biggr) \\&=\biggl(\frac{11405}{11057}\biggr) \\&=\biggl(\frac{348}{11057}\biggr) \\&=\biggl(\frac{2}{11057}\biggr)^2 \biggl(\frac{87}{11057} \biggr) \\&=\biggl(1\biggr)^2 \biggl(\frac{11057}{87} \biggr) \\&=\biggl(\frac{8}{87}\biggr) \\&=\biggl(\frac{2}{87} \biggr)^3 \\&=1 \end{aligned}

Note that the original symbol to evaluate is a Legendre symbol. The interim steps are done with Jacobi symbol as much as possible. With the Jacobi way, the symbol is flipped, reduced and flipped again multiple times. The derivation seems long. However, the flip-reduce-flip is much faster than factoring when the numbers involved are large. $\square$

Example 3
Evaluate $\displaystyle \biggl(\frac{a}{n}\biggr)$ where $n=$ 12408107 and $a=$ 4852777. Both numbers are not prime. The symbol has to be evaluated as a Jacobi symbol.

\displaystyle \begin{aligned} \biggl(\frac{4852777}{12408107}\biggr)&=\biggl(\frac{12408107}{4852777}\biggr) \\&= \biggl(\frac{2702553}{4852777}\biggr) \\&= \biggl(\frac{4852777}{2702553}\biggr) \\&= \biggl(\frac{2150224}{2702553}\biggr) \\&= \biggl(\frac{2}{2702553}\biggr)^4 \biggl(\frac{134389}{2702553}\biggr) \\&= \biggl(1\biggr)^4 \biggl(\frac{2702553}{134389}\biggr) \\&= \biggl(\frac{14773}{134389}\biggr) \\&= \biggl(\frac{134389}{14773}\biggr) \\&= \biggl(\frac{1432}{14773}\biggr) \\&= \biggl(\frac{2}{14773}\biggr)^3 \biggl(\frac{179}{14773}\biggr) \\&= \biggl(-1\biggr)^3 \biggl(\frac{14773}{179}\biggr) \\&= - \biggl(\frac{95}{179}\biggr) \\&= - (-1) \biggl(\frac{179}{95}\biggr) \\&=\biggl(\frac{84}{95}\biggr) \\&=\biggl(\frac{2}{95}\biggr)^2 \biggl(\frac{21}{95}\biggr) \\&=\biggl(1\biggr)^2 \biggl(\frac{95}{21}\biggr) \\&=\biggl(\frac{11}{21}\biggr) \\&=\biggl(\frac{21}{11}\biggr) \\&=\biggl(\frac{10}{11}\biggr) \\&=\biggl(\frac{2}{11}\biggr) \biggl(\frac{5}{11}\biggr) \\&=\biggl(-1\biggr) \biggl(\frac{11}{5}\biggr) \\&=-\biggl(\frac{6}{5}\biggr) \\&=-\biggl(\frac{2}{5}\biggr) \biggl(\frac{3}{5}\biggr) \\&=-\biggl(-1\biggr) \biggl(\frac{5}{3}\biggr) \\&=\biggl(\frac{2}{3}\biggr) \\&=-1 \end{aligned}

The above derivation seems long in that there are quite a few steps. But many of the steps are flip-reduce-flip-reduce that are easy to do. The steps are all done without factoring, except when the top argument is an even number. The Jacobi symbol $\displaystyle \biggl(\frac{a}{n}\biggr)$ is -1. In this case, it gives definite information about the status of quadratic nonresidues. We know for sure that $a$ is a quadratic nonresidue modulo the odd integer $n$, i.e. the equation $x^2 \equiv a \ (\text{mod} \ n)$ has no solutions. $\square$

Example 4
Evaluate $\displaystyle \biggl(\frac{a}{n}\biggr)$ where $n=$ 48746413 and $a=$ 17327467. Both numbers are not prime. As in Example 3, the symbol is evaluated using Jacobi symbol.

\displaystyle \begin{aligned} \biggl(\frac{17327467}{48746413}\biggr) &=\biggl(\frac{48746413}{17327467}\biggr) \\&=\biggl(\frac{14091479}{17327467}\biggr) \\&=-\biggl(\frac{17327467}{14091479}\biggr) \\&=-\biggl(\frac{3236168}{14091479}\biggr) \\&=-\biggl(\frac{2}{14091479}\biggr)^3 \biggl(\frac{404521}{14091479}\biggr) \\&=-\biggl(1\biggr)^3 \biggl(\frac{14091479}{404521}\biggr) \\&=- \biggl(\frac{337765}{404521}\biggr) \\&=- \biggl(\frac{404521}{337765}\biggr) \\&=- \biggl(\frac{66756}{337765}\biggr) \\&=- \biggl(\frac{2}{337765}\biggr)^2 \biggl(\frac{16689}{337765}\biggr) \\&=- \biggl(-1\biggr)^2 \biggl(\frac{337765}{16689}\biggr) \\&=-\biggl(\frac{3985}{16689}\biggr) \\&=-\biggl(\frac{16689}{3985}\biggr) \\&=-\biggl(\frac{749}{3985}\biggr) \\&=-\biggl(\frac{3985}{749}\biggr) \\&=-\biggl(\frac{240}{749}\biggr) \\&=-\biggl(\frac{2}{749}\biggr)^4 \biggl(\frac{15}{749}\biggr) \\&=-\biggl(-1\biggr)^4 \biggl(\frac{749}{15}\biggr) \\&=-\biggl(\frac{14}{15}\biggr) \\&=-\biggl(\frac{-1}{15}\biggr)\\&=-(-1)\\&=1 \end{aligned}

The result of $\displaystyle \biggl(\frac{a}{n}\biggr)=1$ gives ambiguous information about the status of $a=$ 17327467 being a quadratic residue or nonresidue modulo $n=$ 48746413. In this case, the Jacobi symbol cannot tell us whether the equation $x^2 \equiv a \ (\text{mod} \ n)$ has a solution. In such a case, the only way to know the status of quadratic residue is to know some additional information, namely the factoring of the numbers. This example is small enough that $a=$ 3049 x 5683 and $n=$ 7109 x 6857. With this information, the Jacobi symbol can be set up as follows:

\displaystyle \begin{aligned} \biggl(\frac{17327467}{48746413}\biggr) &=\biggl(\frac{17327467}{7109}\biggr) \biggl(\frac{17327467}{6857}\biggr)=(-1) (-1)=1 \end{aligned}

By knowing the factoring of $n$, the original Jacobi symbol is a product of two Legendre symbols. It can be shown that both of these Legendre symbols are -1. These two Legendre symbols corresponds to these two equations: $x^2 \equiv a \ (\text{mod} \ 7109)$ and $x^2 \equiv a \ (\text{mod} \ 6857)$. The Legendre values of -1 indicate that these two equations have no solutions. By the Chinese remainder theorem, the equation $x^2 \equiv a \ (\text{mod} \ 7109 \times 6857)$ has no solutions. Hence $a=$ 17327467 is a quadratic nonresidue modulo $n=$ 48746413=7109 x 6857. $\square$

____________________________________________________________________________

One versatile feature of the Jacobi symbol is that it can be used in evaluating the Legendre symbol, as shown in Example 1 and Example 2. The original Legendre symbol in Example 1 have arguments that are both odd prime and thus can be flipped right away. However, there are numbers in the interim steps that are odd and not prime. With the use of the Jacobi symbol, these interim numbers do have to be factored. The original Legendre symbol in Example 2 has a top argument that is odd and not prime. Treating it as a Jacobi symbol, it can be flipped right away. When numbers involved in Legendre symbol evaluation are large such that the factoring is not obtainable, the Jacobi symbol can be flipped and reduced and flipped again to obtain the answer of the Legendre symbol. The Jacobi symbol plays an outsize role in the evaluation of the Legendre symbol and thus is a pivotal tool in determining whether a number is a quadratic residue modulo an odd prime $p$ or the solvability of the equation $x^2 \equiv a \ (\text{mod} \ p)$.

Example 3 shows that when the Jacobi symbol produces the value of -1, the top argument $a$ is a quadratic nonresidue modulo the lower argument $n$. Example 4 shows that when the Jacobi symbol produces the value of 1, the picture is murky. In such a case, settling the question of whether the top argument $a$ is a quadratic nonresidue modulo the lower argument $n$ requires additional information. Example 4 shows that if we can factor the lower argument $n$, then evaluating the individual Legendre symbols (based on the prime factors) will help answer the original question. This points to the possibility that solving the equation $x^2 \equiv a \ (\text{mod} \ n)$ is not feasible when the factorization of a large composite modulus $n$ is not obtainable.

____________________________________________________________________________
$\copyright \ 2015 \text{ by Dan Ma}$

The Legendre symbol

The law of quadratic reciprocity is a beautiful result. It is also an excellent tool to answer the question: given an odd prime $p$, and given that $a$ is an integer such that $a$ and $p$ are relatively prime, is $a$ is a quadratic residue modulo $p$, in other words, is the equation $x^2 \equiv a \ (\text{mod} \ p)$ solvable? Using the law of quadratic reciprocity requires the evaluation of the Legendre symbol. The focus of this post is on the Legendre symbol as well as related concepts of quadratic residues and the law of quadratic residues. The versatility of the law of quadratic reciprocity is demonstrated with examples.

____________________________________________________________________________

The setting is that the modulus in question is an odd prime $p$. Consider an integer $a$ such that $a$ and $p$ are relatively prime, i.e. having no common prime factor. The number $a$ is said to be a quadratic residue modulo $p$ if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has an integer solution in $x$. Another way to say this is that $a$ is a quadratic residue modulo $p$ if there exists a square root of $a$ modulo $p$ (a square root would be a solution to the equation). If the integer $a$ is not a quadratic residue modulo $p$, we say that $a$ is a quadratic nonresidue modulo $p$. If the context is clear, the word quadratic can be omitted. We can then say $a$ is a residue modulo $p$ or $a$ is a nonresidue modulo $p$.

Since every integer is congruent modulo $p$ to one of the numbers in the set $\mathbb{Z}_p=\left\{0,1,2,\cdots,p-1 \right\}$, the integers $a$ can be considered from the set $\mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\}$ (the non-zero elements of $\mathbb{Z}_p$).

Let’s look at a quick example. Let $p=11$. Squaring each number in $\mathbb{Z}_{11}$ produces the set $\left\{0^2,1^2,2^2,\cdots,10^2 \right\}$. Reducing modulo 11 produces the set $\left\{0,1,4,9,5,3 \right\}$. Thus the integers 1, 3, 4, 5 and 9 are quadratic residues modulo 11. The square roots of each residue are the solutions to the equation $x^2 \equiv a \ (\text{mod} \ 11)$. For $a=3$, the solutions are x = 5 and 6. There are two square roots of 3 modulo 11, namely 5 and 6.

When the modulus is small, it is easy to find all quadratic residues simply by squaring all the numbers in $\mathbb{Z}_p^*$. The focus in this post is on how to use the law of quadratic reciprocity to determine whether a given $a$ is a quadratic residue modulo a large odd prime $p$.

To check whether the integer $a$ is a quadratic residue modulo an odd prime $p$, the most important idea, before considering the law of reciprocity, is to check the modular exponentiation $a^{(p-1)/2} \ (\text{mod} \ p)$. If the result is congruent to 1 modulo $p$, then $a$ is a quadratic residue modulo $p$. If the result is congruent to -1 modulo $p$, then $a$ is a quadratic nonresidue modulo $p$. This is called Euler’s Criterion (proved here). For clarity, it is stated below.

Theorem 1 (Euler’s Criterion)
Let $p$ be an odd prime. Let $a$ be an integer that is relatively prime to $p$. Then the integer $a$ is a quadratic residue modulo $p$ if and only if $\displaystyle a^{(p-1)/2} \equiv 1 \ (\text{mod} \ p)$. On the other hand, the integer $a$ is a quadratic nonresidue modulo $p$ if and only if $\displaystyle a^{(p-1)/2} \equiv -1 \ (\text{mod} \ p)$.

According to Euler’s Criterion, the task of checking for the status of quadratic residue is a matter of performing a modular exponentiation. This can be done using software or a calculator for modular arithmetic. If so desired, the exponentiation can also be programmed using the fast powering algorithm.

Though Euler’s Criterion (with a calculator for modular arithmetic) is a sure fire way for checking the status of quadratic residues, the law of quadratic reciprocity can simplify the task even further. As the examples below will show, checking the status of quadratic residues using the law of reciprocity may require no modular exponentiation at all and if exponentiation is required, it is of a much smaller size.

Theorem 2
Let $p$ be an odd prime. The following properties are true:

• If $a$ and $b$ are both residues modulo $p$, then the product $a \times b$ is a residue modulo $p$.
• If If $a$ and $b$ are both nonresidues modulo $p$, then the product $a \times b$ is a residue modulo $p$.
• If $a$ and $b$ are such that one of them is a residue modulo $p$ and the other is a nonresidue modulo $p$, then the product $a \times b$ is a nonresidue modulo $p$.

Theorem 2 says that the product of two integers of the same types (both residues or both nonresidues) is always a residue modulo the odd prime $p$. The product of two integers of different types is always a nonresidue modulo the odd prime $p$. The theorem follows from Euler’s criterion and from the fact that $(ab)^{(p-1)/2}=a^{(p-1)/2} \times b^{(p-1)/2}$.

In arithmetic modulo a prime $p$, there exists a primitive root modulo $p$ and that any primitive root generates by powering all the integers that are relatively prime to the modulus $p$. Let $g$ be a primitive root modulo an odd prime $p$. It then follows that the quadratic residues modulo $p$ are the even powers of $g$ and the nonresidues are the odd powers of $g$. A related fact is that when $p$ is an odd prime and when $a$ and $p$ are relatively prime, the equation $x^2 \equiv a \ (\text{mod} \ p)$ either has two solutions or has no solutions.

Theorem 3
Let $g$ be a primitive root modulo an odd prime $p$. For any $a$ that is relatively prime to $p$, the following is true:

• $a$ is a quadratic residue modulo $p$ if and only if $a$ is of the form $a \equiv g^{2k} \ (\text{mod} \ p)$ for some positive integer $k$,
• $a$ is a quadratic nonresidue modulo $p$ if and only if $a$ is of the form $a \equiv g^{2k+1} \ (\text{mod} \ p)$ for some positive integer $k$.

Theorem 4
Let $p$ be an odd prime. For any $a$ that is relatively prime to $p$, the equation $x^2 \equiv a \ (\text{mod} \ p)$ either has two solutions or has no solutions (proved here).

____________________________________________________________________________

Legendre Symbol

The law of quadratic reciprocity is stated using the Legendre symbol. For an odd prime $p$ and for an integer $a$ that is relatively prime to $p$, the symbol $\displaystyle \biggl(\frac{a}{p}\biggr)$ is defined as follows:

$\displaystyle \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl} 1 &\ \text{if } a \text{ is a quadratic residue modulo }p\\ -1 &\ \text{if } a \text{ is a quadratic nonresidue modulo }p \end{array} \right.$

One obvious and important observation is that Euler’s Criterion can be restated as follows:

Theorem 1a (Euler’s Criterion)
Let $p$ be an odd prime. Let $a$ be an integer that is relatively prime to $p$. Then $\displaystyle \biggl(\frac{a}{p}\biggr) \equiv \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p)$.

In the above definition, the lower argument of the Legendre symbol is always an odd prime and the upper argument is an integer that is relatively prime to the lower argument. To smooth out some statements involving the Legendre symbol and to make it easier to define the Jacobi symbol in the next post, we relax the Legendre symbol by making $\displaystyle \biggl(\frac{a}{p}\biggr)=0$ whenever $a$ and $p$ are not relatively prime, i.e. $a \equiv 0 \ (\text{mod} \ p)$. The Legendre symbol can be broaden slightly by the following:

$\displaystyle \biggl(\frac{a}{p}\biggr) = \left\{ \begin{array}{rl} 0 &\ \text{if } a \equiv 0 \ (\text{mod} \ p) \\ 1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a \text{ is a quadratic residue modulo }p\\ -1 &\ \text{if } a \not \equiv 0 \ (\text{mod} \ p) \text{ and } a \text{ is a quadratic nonresidue modulo }p \end{array} \right.$

Here’s some useful basic facts about the Legendre symbol.

Theorem 5
Let $p$ be an odd prime. The following properties hold:

• The Legendre symbol is periodic with respect to the top argument, i.e. if $a \equiv b \ (\text{mod} \ p)$, then $\displaystyle \biggl(\frac{a}{p}\biggr)=\biggl(\frac{b}{p}\biggr)$.
• The Legendre symbol is multiplicative with respect to the top argument, i.e. $\displaystyle \biggl(\frac{ab}{p}\biggr)=\biggl(\frac{a}{p}\biggr) \times \biggl(\frac{b}{p}\biggr)$.
• If $a \equiv 0 \ (\text{mod} \ p)$, then $\displaystyle \biggl(\frac{a^2}{p}\biggr)=0$. If $a \not \equiv 0 \ (\text{mod} \ p)$, then $\displaystyle \biggl(\frac{a^2}{p}\biggr)=1$.

The first bullet point in Theorem 5 is easily verified based on the definition of the Legendre symbol. For the case $a \equiv 0 \ (\text{mod} \ p)$, the other facts in Theorem 5 are easily verified. For the case $a \not \equiv 0 \ (\text{mod} \ p)$, the second bullet point follows from Theorem 2, i.e. the fact that the product of two residues and the product of two nonresidues are both residues modulo an odd prime and that the product of a residue and a nonresidue is a nonresidue modulo an odd prime. The second part of the third bullet point is true since any integer that is a square is a quadratic residue.

____________________________________________________________________________

The law of reciprocity can ease the calculation of the Legendre symbol when both the upper and lower arguments are distinct odd primes. Theorem 6 is the law of reciprocity and Theorem 7 and Theorem 8 are two supplements to the law that can round out the calculation. After stating the theorems, we demonstrate with some examples.

Theorem 6 (the law of quadratic reciprocity)

Let $p$ and $q$ be two distinct odd prime numbers. Both of the following statements hold.

$\displaystyle \biggl(\frac{q}{p}\biggr) \displaystyle \biggl(\frac{p}{q}\biggr)=(-1)^{(p-1)/2 \times (q-1)/2}$

Equivalently and more explicitly,

$\displaystyle \biggl(\frac{q}{p}\biggr) = \left\{ \begin{array}{rl} \displaystyle \biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv 1 \ (\text{mod} \ 4) \text{ or } q \equiv 1 \ (\text{mod} \ 4)\\ \displaystyle -\biggl(\frac{p}{q}\biggr) &\ \text{if } p \equiv q \equiv 3 \ (\text{mod} \ 4) \end{array} \right.$

Theorem 7 (first supplement to the law of quadratic reciprocity)

Let $p$ be an odd prime number. The following statement holds.

$\displaystyle \biggl(\frac{-1}{p}\biggr) = (-1)^{(p-1)/2} = \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 4)\\ -1 &\ \text{if } p \equiv 3 \ (\text{mod} \ 4) \end{array} \right.$

Theorem 8 (second supplement to the law of quadratic reciprocity)

Let $p$ be an odd prime number. The following statement holds.

$\displaystyle \biggl(\frac{2}{p}\biggr) =(-1)^{(p^2-1)/8}= \left\{ \begin{array}{rl} 1 &\ \text{if } p \equiv 1 \ (\text{mod} \ 8) \text{ or } p \equiv 7 \ (\text{mod} \ 8)\\ -1 &\ \text{if } p \equiv 3 \ (\text{mod} \ 8) \text{ or } p \equiv 5 \ (\text{mod} \ 8) \end{array} \right.$

Theorem 6 shows how to flip the Legendre symbol if both the upper and lower arguments are distinct odd primes. As long as one of the primes is congruent to 1 modulo 4, we can safely flip the symbol. If both primes are not congruent to 1 modulo 4, we can still flip the symbol except that we have to attach a minus sign. Theorem 7 (the first supplement) indicates when -1 (or $p-1$) is a quadratic residue an odd prime $p$. In words, -1 is a residue modulo $p$ if dividing $p$ by 4 gives the remainder of 1. Otherwise -1 is a nonresidue modulo $p$. Theorem 8 (the second supplement) indicates when 2 is a residue modulo an odd prime $p$. In words, 2 is a residue modulo $p$ if dividing $p$ by 8 leaves a remainder of 1 or 7. Otherwise 2 is a nonresidue modulo $p$.

____________________________________________________________________________

Examples

Example 1
Evaluate $\displaystyle \biggl(\frac{1783}{7523}\biggr)$, an example where both the upper and lower arguments in the Legendre symbol are primes.

\displaystyle \begin{aligned} \biggl(\frac{1783}{7523}\biggr)&=-\biggl(\frac{7523}{1783}\biggr) \\&=-\biggl(\frac{391}{1783}\biggr) \\&=-\biggl(\frac{17}{1783}\biggr) \times \biggl(\frac{23}{1783}\biggr) \\&=-\biggl(\frac{1783}{17}\biggr) \times (-1) \biggl(\frac{1783}{23}\biggr) \\&=\biggl(\frac{15}{17}\biggr) \times \biggl(\frac{12}{23}\biggr) \\&=\biggl(\frac{3}{17}\biggr) \times \biggl(\frac{5}{17}\biggr) \times \biggl(\frac{2}{23}\biggr)^2 \times \biggl(\frac{3}{23}\biggr) \\&=\biggl(\frac{17}{3}\biggr) \times \biggl(\frac{17}{5}\biggr) \times \biggl(1\biggr)^2 \times (-1)\biggl(\frac{23}{3}\biggr) \\&=-\biggl(\frac{2}{3}\biggr) \times \biggl(\frac{2}{5}\biggr) \times \biggl(\frac{2}{3}\biggr) \\&=-\biggl(\frac{2}{5}\biggr) \\&=-(-1) \\&=1 \end{aligned}

The above derivation is a repeated use of Theorems 5, 6 and 8. The idea is to flip the Legendre symbols to make the lower arguments smaller. Then reduce the upper arguments and then factor the upper arguments. Then flip again until reaching a Legendre symbol of $\displaystyle \biggl(\frac{2}{5}\biggr)$, which is easy to solve.

It then follows that 1783 is a quadratic residue modulo the odd prime 7523. The answer can be confirmed by using Euler’s Criterion. Note that $1783^{3761} \equiv 1 \ (\text{mod} \ 7523)$. $\square$

Example 2
Evaluate $\displaystyle \biggl(\frac{a}{p}\biggr)$ where $p=$ 1298351, an odd prime and $a=$ 756479.

The number $a$ is not a prime and is factored as $a=353 \times 2143$. We have the following derivation.

\displaystyle \begin{aligned} \biggl(\frac{756479}{1298351}\biggr)&=\biggl(\frac{353}{1298351}\biggr) \times \biggl(\frac{2143}{1298351}\biggr) \\&=\biggl(\frac{1298351}{353}\biggr) \times (-1)\biggl(\frac{1298351}{2143}\biggr) \\&=-\biggl(\frac{17}{353}\biggr) \times \biggl(\frac{1836}{2143}\biggr) \\&=-\biggl(\frac{17}{353}\biggr) \times \biggl(\frac{2}{2143}\biggr)^2 \times \biggl(\frac{3}{2143}\biggr)^3 \times \biggl(\frac{17}{2143}\biggr) \\&=-\biggl(\frac{353}{17}\biggr) \times \biggl(1\biggr)^2 \times (-1) \biggl(\frac{2143}{3}\biggr)^3 \times \biggl(\frac{2143}{17}\biggr) \\&=\biggl(\frac{13}{17}\biggr) \times \biggl(\frac{1}{3}\biggr)^3 \times \biggl(\frac{1}{17}\biggr) \\&=\biggl(\frac{17}{13}\biggr) \times \biggl(1\biggr)^3 \times \biggl(1\biggr) \\&=\biggl(\frac{4}{13}\biggr) \\&=1 \end{aligned}

The evaluation of the Legendre symbols in this example does not start with a flipping since the upper argument 756479 is not a prime. Instead, we start with factoring the upper argument into prime factors and then proceed with a series of flipping, reducing and factoring. $\square$

Example 3
Evaluate $\displaystyle \biggl(\frac{a}{p}\biggr)$ where $p=$ 569, an odd prime and $a=$ 1610280.

\displaystyle \begin{aligned} \biggl(\frac{1610280}{569}\biggr)&=\biggl(\frac{3}{569}\biggr)^4 \times \biggl(\frac{5}{569}\biggr) \times \biggl(\frac{7}{569}\biggr) \times \biggl(\frac{568}{569}\biggr) \\&= \biggl(\frac{569}{3}\biggr)^4 \times \biggl(\frac{569}{5}\biggr) \times \biggl(\frac{569}{7}\biggr) \times \biggl(\frac{-1}{569}\biggr) \\&= \biggl(\frac{2}{3}\biggr)^4 \times \biggl(\frac{4}{5}\biggr) \times \biggl(\frac{2}{7}\biggr) \times \biggl(1\biggr) \\&= \biggl(-1\biggr)^4 \times \biggl(1\biggr) \times \biggl(1\biggr) \\&=1 \end{aligned}

This example can also be evaluated by first reducing 1610280 modulo 569. $\square$

____________________________________________________________________________

Comment

The law of quadratic reciprocity is a deep and powerful result. It guides the evaluation of Legendre symbols in an attempt to answer whether a number is a quadratic residue modulo an odd prime. The law of reciprocity as represented above requires that the lower argument in the Legendre symbol is an odd prime. When the upper argument is an odd number that is not a prime, there is no way to flip it (based on the law of reciprocity using the Legendre symbol). In Example 2, the evaluation of the Legendre symbol cannot begin until the top argument is factored. The factoring in Example 2 is possible since the number is small. When the number is large, factoring may not always be feasible. It turns out that the Legendre symbol has a generalization, called the Jacobi symbol, that is even more versatile and is defined in the next post.

____________________________________________________________________________
$\copyright \ 2015 \text{ by Dan Ma}$

Speeding up modular exponentiation using CRT

This is the fifth post in a series of posts on the Chinese remainder theorem (CRT). When solving a congruence equation with a composite modulus, it is often easier to convert the problem to one of solving several congruence equations with smaller moduli that are primes or powers of primes. Then combine the individual solutions using the Chinese remainder theorem. In this post, we demonstrate this process for modular exponentiation $x \equiv c^d \ (\text{mod} \ m)$ where the exponent $d$ and the modulus $m$ are large. Given $x \equiv c^d \ (\text{mod} \ m)$, the algorithm discussed here is to produce a system of equations with smaller moduli and exponents that give the same answer as for the original problem.

The previous posts in the series on CRT: first post; second post; third post; fourth post

____________________________________________________________________________

Preliminary discussion

The exponentiation $c^d$ is usually programmed using the fast powering algorithm. The CRT method will convert the exponentiation $c^d$ to several exponentiations that involve much smaller exponents and moduli, thus greatly reducing the calculation time, in particular speeding up the fast powering algorithm. One application of the CRT method is to improve the run time of the decryption process in the RSA algorithm (up to four times faster).

As already mentioned, the goal of the algorithm discussed here is to produce an equivalent system of linear congruence equations. Once this system is produced, the Chinese remainder theorem only guarantees a solution and does not actually produce a solution. So we need to know how to Chinese remainder, i.e. using an algorithm for solving a simultaneous linear congruences. We can use the one discussed here (the first method) or here (the second method). The following examples are worked using the second method.

The CRT algorithm discussed here makes use of Euler’s theorem, which states that $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ whenever $a$ and the modulus $m$ are relatively prime where $\phi(m)$ is the phi function evaluated at $m$. For this reason, the algorithm requires the evaluation of the phi function.

When calculating $c^d \ (\text{mod} \ m)$, the use of the phi function $\phi(m)$ is to reduce the exponent $d$ by the largest multiple of $\phi(m)$. For example, since $\phi(17)=16$ and $2^{16} \equiv 1 \ (\text{mod} \ 17)$, the problem of $2^{250} \ (\text{mod} \ 17)$ is converted to finding $2^{10} \ (\text{mod} \ 17)$. Here, the original exponent of 250 is reduced to 10 after taking out the largest multiple of 16. Note that $10 \equiv 250 \ (\text{mod} \ \phi(17)=16)$. In general, we want to replace the original exponent $d$ by a smaller exponent $d_1$ where $d_1 \equiv d \ (\text{mod} \ \phi(m))$.

____________________________________________________________________________

Examples

In the following three examples, we use the algorithm discussed here to solve systems of linear congruence equations (this is the iterative approach). These examples are by no means realistic since the numbers used are small. So they are for demonstration of how CRT works.

Example 1
Calculate $x \equiv 2^{3163} \ (\text{mod} \ 3969)$.

First, factor the modulus $3969=3^4 \times 7^2=81 \times 49$. Now the problem is converted to solving the following system of two equations:

$x \equiv 2^{3163} \ (\text{mod} \ 81)$

$x \equiv 2^{3163} \ (\text{mod} \ 49)$

By CRT, any solution to the two equations is also a solution to the original equation. However, the exponent of 3163 should first be reduced. To this end, calculate the phi function, where $\phi(3^4)=3^2 \cdot (3-1)=54$ and $\phi(7^2)=7 \cdot (7-1)=42$. We should reduce from 3163 the largest multiple of 54 in the first equation and reduce the largest multiple of 42 in the second equation. In other words, reduce the exponent 3163 modulo the two phi function values:

$3163 \equiv 31 \ (\text{mod} \ 54)$

$3163 \equiv 13 \ (\text{mod} \ 42)$

As a result, we solve the following two equations:

$x \equiv 2^{3163} \equiv 2^{31} \equiv 65 \ (\text{mod} \ 81)$

$x \equiv 2^{3163} \equiv 2^{13} \equiv 9 \ (\text{mod} \ 49)$

Note that the original exponentiation $2^{3163}$ is turned into the easier ones of $2^{31}$ and $2^{13}$. The following gives the solution to the above two equations.

\displaystyle \begin{aligned} x_0&=65+81 \cdot 23 \cdot (9-65) \ (\text{mod} \ 3969) \\&\equiv -104263 \ (\text{mod} \ 3969) \\&\equiv 2900 \ (\text{mod} \ 3969) \end{aligned}

where 23 is obtained by solving for $y$ in $81y \equiv 1 \ (\text{mod} \ 49)$

By CRT, the answer to the original problem is $2^{3163} \equiv 2900 \ (\text{mod} \ 3969)$. $\square$

Example 2
Calculate $x \equiv 3^{3163} \ (\text{mod} \ 3969)$.

In this example, the number 3 and the modulus 3969 are not relatively prime. The CRT method still applies. As in Example 1, the problem can be reduced in the following way:

$x \equiv 3^{3163} \equiv 3^{31} \equiv 0 \ (\text{mod} \ 81)$

$x \equiv 2^{3163} \equiv 3^{13} \equiv 10 \ (\text{mod} \ 49)$

The first equation is congruent to 0 since $3^{31}$ contains 81 as a factor. The following gives the solution to the above two equations:

\displaystyle \begin{aligned} x_0&=0+81 \cdot 23 \cdot (10-0) \ (\text{mod} \ 3969) \\&\equiv 18630 \ (\text{mod} \ 3969) \\&\equiv 2754 \ (\text{mod} \ 3969) \end{aligned}

By CRT, the answer to the original problem is $3^{3163} \equiv 2754 \ (\text{mod} \ 3969)$. $\square$

Example 3
The above 2 examples use small numbers to illustrate the CRT technique. In this example, we use slightly larger numbers. Calculate $x \equiv 355^{d} \ (\text{mod} \ m)$ where $d=\text{1,759,695,794}$ and $m=\text{3,055,933,789}=1277 \cdot 1439 \cdot 1663$.

As in the other examples, we break up the problem in three congruences. The three factors of the modulus are prime numbers. Thus we reduce the exponent $d$ by multiples of a prime factor less one.

$\text{1,759,695,794} \equiv 1198 \ (\text{mod} \ 1276)$

$\text{1,759,695,794} \equiv 814 \ (\text{mod} \ 1438)$

$\text{1,759,695,794} \equiv 110 \ (\text{mod} \ 1662)$

Then the original problem is transformed to solving the following three equations.

$x \equiv 355^{d} \equiv 355^{1198} \equiv 189 \ (\text{mod} \ 1277)$

$x \equiv 355^{d} \equiv 355^{814} \equiv 1010 \ (\text{mod} \ 1439)$

$x \equiv 355^{d} \equiv 355^{110} \equiv 315 \ (\text{mod} \ 1663)$

Notice that the original exponentiation is transformed to the smaller ones of $355^{1198}$, $355^{814}$ and $355^{315}$. The remaining task is to solve the system of three equations. One way to find to solution to the above three equations is to use the iterative approach, starting with the solution $x_1=189$ to the first equation. Then find the solution $x_2$ to the first two equations and then the solution $x_3$ to all three equations.

\displaystyle \begin{aligned} x_2&=189+1277 \cdot 151 \cdot (1010-189) \ (\text{mod} \ 1277 \cdot 1439) \\&\equiv 158311156 \ (\text{mod} \ 1837603) \\&\equiv 277298 \ (\text{mod} \ 1837603) \end{aligned}

where 151 is obtained by solving for $y$ in $1277y \equiv 1 \ (\text{mod} \ 1439)$

\displaystyle \begin{aligned} x_3&=277298+(1277 \cdot 1439) \cdot 970 \cdot (315-277298) \ (\text{mod} \ 1277 \cdot 1439 \cdot 1663) \\&\equiv 277298+1782474910 \cdot (-276983) \ (\text{mod} \ m) \\&\equiv 277298+1414954310 \ (\text{mod} \ m) \\&\equiv 1415231608 \ (\text{mod} \ m) \end{aligned}

where 970 is obtained by solving for $y$ in $(1277 \cdot 1439) y \equiv 1 \ (\text{mod} \ 1663)$

By CRT, the answer to the original problem is $355^{d} \equiv 1415231608 \ (\text{mod} \ m)$. $\square$

____________________________________________________________________________

The CRT algorithm to speed exponentiation

Suppose we wish to evaluate $x \equiv c^{d} \ (\text{mod} \ m)$ where the prime factorization of $m$ is $m=p_1^{n_1} \cdot p_2^{n_2} \cdots p_t^{n_t}$. The numbers $p_i$ are distinct prime numbers and each exponent $n_i \ge 1$. To prepare for the calculation, do the following:

Let $m_i=p_i^{n_i}$ for each $i$.

Calculate $\phi(m_i)$ for each $i$.

Case 1. The base $c$ and the modulus $m$ are relatively prime.
Then the answer to the original exponentiation problem is identical to the solution to the following system of $t$ congruence equations:

$x \equiv c^{d_1} \ (\text{mod} \ m_1)$

$x \equiv c^{d_2} \ (\text{mod} \ m_2)$

$\cdots$

$x \equiv c^{d_t} \ (\text{mod} \ m_t)$

where $d_i \equiv d \ (\text{mod} \ \phi(m_i))$ for each $i$. If possible, each $c^{d_i}$ should be reduced modulo $m_i$.

Case 2. The base $c$ and the modulus $m$ are not relatively prime.
In this case, $c$ and $m$ have prime factors in common (at least one $p_i$). The idea here is that for any $p_i$ that is a prime factor of $c$, the equation $x \equiv c^{d_i} \ (\text{mod} \ m_i)$ in Case 1 is replaced by $x \equiv 0 \ (\text{mod} \ m_i)$. Then solve the resulting system of equations (see Example 2). Essentially, Case 2 can fall under Case 1 with $c^{d_i}$ being congruent to zero. We call out Case 2 for the sake of clarity.

The original exponentiation $c^d$ boils down to solving an appropriate system of CRT congruences as described above. Once the equivalent system of congruences is set up, use the algorithm discussed here or here to do Chinese remaindering.

Comment
Both Case 1 and Case 2 produce a system of linear congruence equations that have identical solution to the original equation. This is a result of using CRT (see Theorem D and Theorem G here). The savings in the calculation come in the form of the smaller exponentiations in the resulting congruence equations.

In Case 2, some of the congruence equations are $x \equiv 0$. This is because the base $c$ and some moduli $m_i$ are not relatively prime. For these moduli, $c^{d_i}$ would contain $p_i^{n_i}$ as a factor (assuming that $d_i \ge n_i$). Hence, $x \equiv c^{d_i} \equiv 0 \ (\text{mod} \ m_i)$.

The two-equation case
When the modulus is the product of two factors that are relatively prime, the CRT algorithm involves only two equations. We write out the solution explicitly for this case. To evaluate $x \equiv c^{d} \ (\text{mod} \ m)$ where $m=m_1 \cdot m_2$ and $m_1$ and $m_2$ are relatively prime, solve the following system of two equations,

$x \equiv c^{d_1} \ (\text{mod} \ m_1)$

$x \equiv c^{d_2} \ (\text{mod} \ m_2)$

The solution is $x \equiv c^{d_1}+m_1 \cdot v_1 \cdot (c^{d_2}-c^{d_1}) \ (\text{mod} \ m)$ where $v_1$ is the multiplicative inverse of $m_1$ modulo $m_2$. If possible, each $c^{d_i}$ should be reduced modulo $m_i$.

____________________________________________________________________________

RSA application

The algorithm to speed the exponentiation is possible because the factorization of the modulus $m$ is known (as a result, the values of $\phi(m_i)$ are known). Knowing the values of $\phi(m_i)$ makes it possible to reduce the large exponent $d$. For this reason, the decryption process in the RSA algorithm is a perfect place to apply the CRT technique described here.

With the RSA cryptosystem, a public key consists of $N$ and $e$, where $N$ is a large modulus that is a product of two large primes $p$ and $q$ (the two primes are not published) and $e$ is the encryption exponent. Say Bob is the originator of the RSA public key. Bob also generates a private key, which is a number $d$ that is used for decrypting any messages that he receives. The number $d$ must be kept private. The prime factors $p$ and $q$ must also be kept secret since knowing $p$ and $q$ can derive $d$.

Suppose that Alice has a message to send to Bob. She can do so using the published key of $N$ and $e$ through the exponentiation $c \equiv m^e \ (\text{mod} \ N)$. Here, $m$ is the plaintext (the message to be sent) and $c$ is the ciphertext (the encrypted message). Upon receiving the ciphertext $c$, Bob can then decrypt through the exponentiation $m \equiv c^d \ (\text{mod} \ N)$ where $d$ is the decryption exponent. In realistic RSA calculation, the public modulus $N$ and the private decryption exponent $d$ are large integers ($N$ is at minimum a 2048-bit number). With CRT, the decryption can be reduced to two much smaller exponentiations. The effect can be at least four times faster.

We illustrate this with an example. This is a toy example since the numbers used are small. It is only intended as an illustration.

Example 4
Suppose the public key consists of $N=\text{17,086,049}$ and $e=65537$. Bob has the additional information of $N=p \cdot q$ where $p=3863$ and $q=4423$, which are kept secret. Knowing $p$ and $q$ allows Bob to compute $d=\text{5,731,241}$. Suppose that Bob receives a message $c=$ 4831984 from Alice. Use the CRT approach to find the plaintext $m$.

The exponentiation is $m \equiv 4831984^{5731241} \ (\text{mod} \ N)$, which is equivalent to the following two equations by CRT:

$m \equiv 4831984^{5731241} \ (\text{mod} \ 3863)$

$m \equiv 4831984^{5731241} \ (\text{mod} \ 4423)$

which is further simplified to:

$m \equiv 4831984^{5731241} \equiv 4831984^{33} \equiv 3084 \ (\text{mod} \ 3863)$

$m \equiv 4831984^{5731241} \equiv 4831984^{329} \equiv 1436 \ (\text{mod} \ 4423)$

where $33 \equiv 5731241 \ (\text{mod} \ 3862)$ and $329 \equiv 5731241 \ (\text{mod} \ 4422)$. Then the following is the plaintext (the original message).

\displaystyle \begin{aligned} m&=3084+3863 \cdot 1319 \cdot (1436-3084) \ (\text{mod} \ 3863 \cdot 4423) \\&\equiv 3084+5095297 \cdot (-1648) \ (\text{mod} \ N) \\&\equiv 9289736 \ (\text{mod} \ N) \end{aligned}

where 1319 is obtained by solving for $y$ in $3683y \equiv 1 \ (\text{mod} \ 4423)$

The answer is $4831984^{5731241} \equiv 9289736 \ (\text{mod} \ N)$. $\square$

____________________________________________________________________________

Closing comment

In conclusion, we state the explcit formula for providing the CRT answer to the RSA decryption.

$m \equiv c^{d_p}+p \cdot p_{inv} \cdot (c^{d_q}-c^{d_p}) \ (\text{mod} \ p \cdot q) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

where $d_p \equiv d \ (\text{mod} \ p-1)$, $d_q \equiv d \ (\text{mod} \ q-1)$ and $p_{inv}$ is the multiplicative inverse of $p$ modulo $q$.

The decryption formula of (1) represends tremendous saving in calculation (up to four times faster). It is possible only for the holder of the RSA private key. It requires knowledge of the decryption exponent $d$, which is calculated from the factors $p$ and $q$ of the modulus $N$.
____________________________________________________________________________
$\copyright \ 2015 \text{ by Dan Ma}$

How to Chinese remainder, part 2

This is the fourth post in a series of posts on the Chinese remainder theorem (usually abbreviated as CRT). The previous post presents an algorithm for solving systems of linear congruence equations, which is based on a constructive proof of CRT. This post presents another algorithm that is based on another constructive proof of CRT. Links to the previous posts in the series: first post, second post, third post.

The algorithm discussed here is to solve the following is the version of the Chinese remainder theorem. This version has been shown to be equivalent to several other versions in this previous post.

Theorem G (Chinese Remainder Theorem)
Suppose $m_1,m_2,\cdots,m_t$ are positive integers that are pairwise relatively prime. Let $m=m_1 \cdot m_2 \cdots m_t$. For any sequence of integers $c_1,c_2,\cdots,c_t$, the following system of linear congruence equations

$x \equiv c_1 \ (\text{mod} \ m_1)$

$x \equiv c_2 \ (\text{mod} \ m_2)$

$\cdots$

$x \equiv c_{t-1} \ (\text{mod} \ m_{t-1})$

$x \equiv c_t \ (\text{mod} \ m_t)$

has a unique solution modulo $m=m_1 \cdot m_2 \cdots m_t$.

____________________________________________________________________________

Discussion of Proof/Algorithm

To understand the algorithm, it is a good idea to understand the constructive proof of CRT on which the algorithm is based. The constructive proof is to build up a solution to the system of equations in CRT in an iterative fashion. The first equation (stated in the above statement of CRT) has a solution, which is $x_1=c_1$. Then the solution $x_1$ is used to build a solution to the first two equations, say $x_2$, which is then used to build the solution to the first three equations, and so on. So this constructive proof of a solution is an inductive proof.

Let’s look at the case of two equations: $x \equiv c_1 \ (\text{mod} \ m_1)$ and $x \equiv c_2 \ (\text{mod} \ m_2)$. Then $x_1=c_1$ is the solution to the first equation. Express the equation $x_1 \equiv c_1 \ (\text{mod} \ m_1)$ as $c_1=x_1+m_1 y$ for some integer $y$. We would like $x_1+m_1 y$ to be the solution to the second equation too. Then we need to solve for $y$ in the following equation

$x_1+m_1 \cdot y \equiv c_2 \ (\text{mod} \ m_2) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

Once we know what $y$ is, $x_1+m_1 \cdot y$ is the desired solution to the system of two equations. To solve for $y$, subtract $x_1$ on both sides of (*) and then multiply both sides by the inverse of $m_1$. Then $y=v_1 \cdot (c_2-x_1)$ where $v_1$ is the multiplicative inverse of $m_1$ modulo $m_2$. The desired solution is $x_2$ where $x_2=x_1+m_1 \cdot v_1 \cdot (c_2-x_1)$. From the way it is set up, $x_2$ is a solution to both equations.

Let’s look at the case of $t$ equations as described in the statement of Theorem F. Let $x_{t-1}$ be the solution to the first $t-1$ equations. We will use this to build $x_{t}$, the solution to all the $t$ equations. The key is to solve for $y$ in the equation

$x_{t-1}+m_1 \cdot m_2 \cdots m_{t-1} \cdot y \equiv c_{t} \ (\text{mod} \ m_{t})$

Then $y=v_{t-1} \cdot (c_{t}-x_{t-1})$ where $v_{t-1}$ is the multiplicative inverse of $m_1 \cdot m_2 \cdots m_{t-1}$ modulo $m_{t}$. Then the following

$x_{t}=x_{t-1}+(m_1 \cdot m_2 \cdots m_{t-1}) \cdot v_{t-1} \cdot (c_{t}-x_{t-1})$

It is clear that $x_{t} \equiv x_{t-1} \equiv c_i \ (\text{mod} \ m_i)$ for $i=1,\cdots,t-1$. This is because the term $(m_1 \cdot m_2 \cdots m_{t-1}) \cdot v_{t-1} \cdot (c_{t}-x_{t-1})$ in $x_{t}$ vanishes. From the way $x_{t}$ is set up, it is clear that $x_{t} \equiv c_{t} \ (\text{mod} \ m_{t})$.

The inductive argument just presented establishes that the system of linear congruence equations in Theorem F always has a solution. An algorithm can be created based on this inductive proof.

____________________________________________________________________________

An algorithm for CRT

Assume that the system has $t$ equations, as described and notated in the statement of Theorem F above. The algorithm is then to build a series of numbers

$x_1, x_2, \cdots, x_j, \cdots, x_t \ \ \ \ \ \ 2 \le j \le t$

leading to the desired solution $x_t$ where $x_1=c_1$ and $x_j$ is the solution to the first $j$ equations and is obtained using $x_{j-1}$ as follows:

$x_{j}=x_{j-1}+(m_1 \cdot m_2 \cdots m_{j-1}) \cdot v_{j-1} \cdot (c_{j}-x_{j-1}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

$v_{j-1}$ is defined such that $(m_1 \cdot m_2 \cdots m_{j-1}) \cdot v_{j-1} \equiv 1 \ (\text{mod} \ m_j)$

Note that the number $v_{j-1}$ is the multiplicative inverse of $m_1 \cdot m_2 \cdots m_{j-1}$ modulo $m_j$. The desired solution $x_t$ may have to be reduced modulo $m=m_1 \cdot m_2 \cdots m_{t}$.

In a computer implementation, the algorithm in $(1)$ is carried out iteratively to find the solution. If the calculation is to be carried by hand as an exercise, an alternative to memorizing the formula $(1)$ is to know that each step $x_{j}$ is obtained from solving for $y$ in the following equation:

$x_j \equiv x_{j-1}+m_1 \cdot m_2 \cdots m_{j-1} \cdot y \equiv c_{j} \ (\text{mod} \ m_{j})$

Comment
If there are $t$ equations, the algorithm as described here requires the finding of $t-1$ applications of the extended Euclidean algorithm (for the multiplicative inverse in each induction step). If the given equations are in the form $a_i \cdot x \equiv b_i \ (\text{mod} \ m_i)$, then $t$ additional applications of the extended Euclidean algorithm are required to convert the equations to the form $x \equiv c_i \ (\text{mod} \ m_i)$. Overall, the amount of computation is comparable to the algorithm discussed in the previous post.

The iterative nature of this algorithm is useful in the situations where the solution to a smaller system is known. For example, if we add an additional equation to an existing system of equations, then the solution to the new system can be found based on the solution to the smaller system. In particular, with one additional application of the extended Euclidean algorithm, the new solution can be found. The following two examples demonstrate how this works.

____________________________________________________________________________

Examples

Example 1
Solve the following system of linear congruence equations.

$x \equiv 3 \ (\text{mod} \ 17)$

$x \equiv 10 \ (\text{mod} \ 21)$

$x \equiv 15 \ (\text{mod} \ 29)$

This is Example 1 from this previous post. The results are $x_1=3$, $x_2=241$ and $x_3=7381$ as derived below:

\displaystyle \begin{aligned} x_2&\equiv 3+17 \cdot 5 \cdot (10-3) \ (\text{mod} \ 17 \cdot 21) \\&\equiv 598 \ (\text{mod} \ 357) \\&\equiv 241 \ (\text{mod} \ 357) \end{aligned}

where 5 is obtained by solving $17y \equiv 1 \ (\text{mod} \ 21)$

\displaystyle \begin{aligned} x_3&\equiv 241+(17 \cdot 21) \cdot 13 \cdot (15-241) \ (\text{mod} \ 17 \cdot 21 \cdot 29) \\&\equiv -1048625 \ (\text{mod} \ 10353) \\&\equiv 7381 \ (\text{mod} \ 10353) \end{aligned}

where 13 is obtained by solving $(17 \cdot 21) y \equiv 1 \ (\text{mod} \ 29)$

Example is now completed. $\square$

Example 2
To illustrate the iterative nature of the algorithm, we add an addition equation to the system in Example 1. Solve the following system of linear congruence equations.

$x \equiv 3 \ (\text{mod} \ 17)$

$x \equiv 10 \ (\text{mod} \ 21)$

$x \equiv 15 \ (\text{mod} \ 29)$

$x \equiv 16 \ (\text{mod} \ 31)$

From Example 1, the solution to the first three equations is $x_3=7381 \ (\text{mod} \ 10353)$ where 10353 is the product of the first three moduli. The following gives the solution:

\displaystyle \begin{aligned} x_4&\equiv 7381+10353 \cdot 30 \cdot (16-7381) \ (\text{mod} \ 17 \cdot 21 \cdot 29 \cdot 31) \\&\equiv -2287487969 \ (\text{mod} \ 320943) \\&\equiv 193735 \ (\text{mod} \ 320943) \end{aligned}

where 30 is obtained by solving $10353 y \equiv 1 \ (\text{mod} \ 31)$

The above gives the unique solution to the given system of linear equations. $\square$

____________________________________________________________________________
$\copyright \ 2015 \text{ by Dan Ma}$

How to Chinese remainder, part 1

This is the third post in a series of posts on the Chinese remainder theorem (first post and second post). In this and the next post, we highlight two algorithms for obtaining the solution of a system of linear congruence equations. The Chinese remainder theorem guarantees that, under certain condition, any system of linear congruence equations has a unique solution (unique modulo the product of all the moduli of the congruence equations). The theorem is usually abbreviated as CRT. Even though the solution is unique, there are more than one way to solve systems of simultaneous linear congruence equations. In this post, we extract an algorithm from a constructive proof of CRT that is found in many textbooks (used here in this previous post). In the next post, we present another algorithm for solving systems of linear congruence equations.

The statement of CRT only guarantees the existence of a solution and does not show how to derive the unique solution. In many situations, it is sufficient to know that solutions exist (e.g. using CRT to prove theorems). In other situations where actual solutions are sought, we need more than the statement of CRT. In these situations, an algorithm is needed to actually find a solution. It is critical to have an algorithm for solving CRT problems, especially in computer implementation.

The algorithm discussed here is to solve the following is the version of the Chinese remainder theorem. This version has been shown to be equivalent to several other versions in this previous post.

Theorem F (Chinese Remainder Theorem)
Suppose $m_1,m_2,\cdots,m_t$ are positive integers that are pairwise relatively prime. Let $m=m_1 \cdot m_2 \cdots m_t$. Suppose we have the following system of linear congruence equations

$a_1 \ x \equiv b_1 \ (\text{mod} \ m_1)$

$a_2 \ x \equiv b_2 \ (\text{mod} \ m_2)$

$\cdots$

$a_{t-1} \ x \equiv b_{t-1} \ (\text{mod} \ m_{t-1})$

$a_t \ x \equiv b_t \ (\text{mod} \ m_t)$

such that each of the linear congruence equations has a unique solution, i.e. for each $i$, $a_i$ and $m_i$ are relatively prime. Then the system of linear congruence equations has a unique solution modulo $m=m_1 \cdot m_2 \cdots m_t$.

____________________________________________________________________________

Examples

Example 1
Solve the following system of linear congruence equations.

$x \equiv 3 \ (\text{mod} \ 17)$

$x \equiv 10 \ (\text{mod} \ 21)$

$x \equiv 15 \ (\text{mod} \ 29)$

Both 17 and 29 are prime. The factors of 21 are 3 and 7. The three moduli are pairwise relatively prime (i.e. no two of which have a common factor other than 1). Thus CRT implies that the three equations have a solution $x_0$. The solution is unique modulo 10353 = 17 x 21 x 29. This means that if $y$ is another solution, then $y\equiv x_0 \ (\text{mod} \ 10353)$.

The solution is $x_0=3 \cdot 609 \cdot 11+10 \cdot 493 \cdot 19+15 \cdot 357 \cdot 13 \ (\text{mod} \ 10353)$ where

$609=21 \cdot 29$ and $609 \cdot 11 \equiv 1 \ (\text{mod} \ 17)$

$493=17 \cdot 29$ and $493 \cdot 19 \equiv 1 \ (\text{mod} \ 21)$

$357=17 \cdot 21$ and $357 \cdot 13 \equiv 1 \ (\text{mod} \ 29)$

The number 609 is the product of the remaining moduli (all the modulo not 17). Because 609 and the modulus 17 are relatively prime, the number 609 has a multiplicative inverse modulo 17. The multiplicative inverse is 11, found using the extended Euclidean algorithm. The other two pairs “493 and 19” and “357 and 13” are found similarly. Thus the solution $x_0$ is the sum of three numbers. The first is 3 x 609 x 11, where 3 is the solution to the first equation, and 609 and 11 multiplicative inverses to each other modulo 17. The other two numbers 10 x 493 x 19 and 15 x 357 x 13 are obtained similarly.

After reducing modulo 10353, the solution is

\displaystyle \begin{aligned} x_0&\equiv 3 \cdot 609 \cdot 11+10 \cdot 493 \cdot 19+15 \cdot 357 \cdot 13 \ (\text{mod} \ 10353) \\&\equiv 20097+93670+69615 \ (\text{mod} \ 10353) \\&\equiv 9744+493+7497 \ (\text{mod} \ 10353) \\&\equiv 17734 \ (\text{mod} \ 10353) \\&\equiv 7381 \ (\text{mod} \ 10353) \end{aligned}

The algorithm demonstrated here requires the computation of three multiplicative inverses. One try and true method for finding multiplicative inverse in the extended Euclidean algorithm (i.e. applying the Euclidean algorithm and then work backward). We demonstrate how to solve $609y \equiv 1 \ (\text{mod} \ 17)$. To this end, solve the linear diophantine equation $609y+17z=1$. Then work backward.

\displaystyle \begin{aligned} &609=17 \cdot 35+1 \\&17=14 \cdot 1+3 \\&14=3 \cdot 4+2 \\&3=2 \cdot 1+1 \\&2=1 \cdot 2+0 \\&\text{ } \\&\text{ } \end{aligned} \ \ \ \ \ \ \ \ \ \displaystyle \begin{aligned} 1&=3-2 \\&=3-(14-3 \cdot 4) \\&=14(-1)+3(5) \\&=14(-1)+(17-14)5 \\&=17(5)+14(-6) \\&=17(5)+(609-17 \cdot 35) (-6) \\&=609(-6)+17(215) \end{aligned}

The calculation on the left shows the repeated applications of divisions to show that $(609,17)=1$. The calculation on the right works backward to solve $609y+17z=1$. The solution is $y=-6$, the least residue of which is $y=11$. $\square$

Example 2
Solve the following system of linear congruence equations.

$3 \ x \equiv 1 \ (\text{mod} \ 5)$

$4 \ x \equiv 6 \ (\text{mod} \ 14)$

$5 \ x \equiv 11 \ (\text{mod} \ 3)$

The algorithm used in Example 1 works here. The only difference is that each equation needs to be solved individually. The numbers here are small. The equations can be solved by inspection. Otherwise, each equation can also be solved by solving an appropriate linear diophantine equation (as discussed here). The following are the solutions to the above equations (individually).

$x \equiv 2 \ (\text{mod} \ 5)$

$x \equiv 5 \ (\text{mod} \ 14)$

$x \equiv 1 \ (\text{mod} \ 3)$

The problem is then to solve the system of the above 3 linear congruence equations. The solution is $x_0=2 \cdot 42 \cdot 8+5 \cdot 15 \cdot 1+1 \cdot 70 \cdot 1$ where:

$42=14 \cdot 3$ and $42 \cdot 8 \equiv 1 \ (\text{mod} \ 5)$

$15=5 \cdot 3$ and $15 \cdot 1 \equiv 1 \ (\text{mod} \ 14)$

$70=5 \cdot 14$ and $70 \cdot 1 \equiv 1 \ (\text{mod} \ 3)$

The above calculation requires solving three linear congruence equations individually and finding three multiplicative inverses. Both tasks can be done using the extended Euclidean algorithm. After further reduction modulo 210, the unique solution is:

\displaystyle \begin{aligned} x_0&\equiv 2 \cdot 42 \cdot 8+5 \cdot 15 \cdot 1+1 \cdot 70 \cdot 1 \ (\text{mod} \ 210) \\&\equiv 672+75+70 \ (\text{mod} \ 210) \\&\equiv 42+75+70 \ (\text{mod} \ 210) \\&\equiv 187 \ (\text{mod} \ 210) \end{aligned}

The above gives the unique solution to the given system of linear equations. $\square$

____________________________________________________________________________

An algorithm for CRT

Now we describe the algorithm that is described by the above two examples. Suppose that the following system of equations such that the moduli $m1,m_2,\cdots,m_t$ are pairwise relatively prime and such that each equation by itself has a unique solution, i.e. $a_i$ and $m_i$ are relatively prime for each $i$.

$a_1 \ x \equiv b_1 \ (\text{mod} \ m_1)$

$a_2 \ x \equiv b_2 \ (\text{mod} \ m_2)$

$\cdots$

$a_{t-1} \ x \equiv b_{t-1} \ (\text{mod} \ m_{t-1})$

$a_t \ x \equiv b_t \ (\text{mod} \ m_t)$

The following three steps describe how to obtain the solution to this system of equations.

Step 1
Solve each equation $a_i \ x \equiv b_i \ (\text{mod} \ m_i)$ individually to obtain the solution $x \equiv c_i \ (\text{mod} \ m_i)$. The original system is equivalent to the following equivalent system of equations, i.e. any solution to one system is the solution to the other.

$x \equiv c_1 \ (\text{mod} \ m_1)$

$x \equiv c_2 \ (\text{mod} \ m_2)$

$\cdots$

$x \equiv c_{t-1} \ (\text{mod} \ m_{t-1})$

$x \equiv c_t \ (\text{mod} \ m_t)$

Step 2
For each $i$, let $n_i$ be the product of all moduli $m_j$ where $j \ne i$. Each $n_i$ is relatively prime to $m_i$. Thus $n_i$ has a multiplicative inverse modulo $m_i$. Equivalently solve the following equations individually.

$n_1 \ y \equiv 1 \ (\text{mod} \ m_1)$

$n_2 \ y \equiv 1 \ (\text{mod} \ m_2)$

$\cdots$

$n_{t-1} \ y \equiv 1 \ (\text{mod} \ m_{t-1})$

$n_t \ y \equiv 1 \ (\text{mod} \ m_t)$

For each $i$, let $w_i$ be the inverse of $n_i$ modulo $m_i$, i.e. $n_i^{-1} \equiv w_i \ (\text{mod} \ m_i)$.

Step 3
The solution is given by

$x_0 \equiv c_1 \cdot n_1 \cdot w_1+c_2 \cdot n_2 \cdot w_2+\cdots+c_t \cdot n_t \cdot w_t \ (\text{mod} \ m)$

where $m=m_1 \cdot m_2 \cdots m_t$.

Let’s look at what the algorithm entails computationally. Step 1 requires solving a set of linear congruence equations individually (equivalently, solving linear diophantine equations individually), unless the equations are given in the form $x \equiv c_i \ (\text{mod} \ m_i)$. The extended Euclidean algorithm is an excellent approach, especially in computer implementation.

Step 2 involves finding multiplicative inverses of the numbers $n_i$. The extended Euclidean algorithm is also an excellent approach, especially in computer implementation.

Step 3 is to gather up the results from Step 1 and Step 2. The computation here is to reduce modulo $m=m_1 \cdot m_2 \cdots m_t$.

____________________________________________________________________________

Why does the algorithm work?

The number $x_0 \equiv c_1 \cdot n_1 \cdot w_1+c_2 \cdot n_2 \cdot w_2+\cdots+c_t \cdot n_t \cdot w_t \ (\text{mod} \ m)$ is a solution to each of the equations in the given system of linear congruence equations. To see that $x_0$ is a solution to the equation $a_1 \ x \equiv b_1 \ (\text{mod} \ m_1)$, note that:

\displaystyle \begin{aligned} a_1 \cdot x_0&\equiv a_1 \cdot (c_1 \cdot n_1 \cdot w_1+c_2 \cdot n_2 \cdot w_2+\cdots+c_t \cdot n_t \cdot w_t) \\&\equiv a_1 \cdot c_1 \cdot n_1 \cdot w_1+a_1 \cdot c_2 \cdot n_2 \cdot w_2+\cdots+a_1 \cdot c_t \cdot n_t \cdot w_t \\&\equiv a_1 \cdot c_1 \cdot n_1 \cdot w_1 \\&\equiv a_1 \cdot c_1 \\&\equiv b_1 \ (\text{mod} \ m_1) \end{aligned}

In the above derivation, all the terms containing $n_j$ with $j \ne 1$ drop out. This is because $n_j$ has $m_1$ as a factor. The product $n_1 \cdot w_1$ drops out since $w_1$ is the multiplicative inverse if $n_1$ modulo $m_1$. Finally $a_1 \cdot c_1 \equiv b_1 \ (\text{mod} \ m_1)$ since $c_1$ is a solution of the equation $a_1 \ x \equiv b_1 \ (\text{mod} \ m_1)$. By the same reasoning, $x_0$ is the solution to all the other equations in the system.

To see that the solution $x_0$ is unique, see the proof in this previous post.

____________________________________________________________________________
$\copyright \ 2015 \text{ by Dan Ma}$

Versions of the Chinese remainder theorem

This post is the second post in a series of posts on the Chinese remainder theorem (CRT). The previous post sets up the scene by discussing the fundamental theorem of arithmetic. In this post, we derive the various versions of CRT from a lemma (Lemma A below) that is equivalent to the fundamental theorem of arithmetic.

Links to the other posts in the series: first post, third post, fourth post.

____________________________________________________________________________

The starting point

Lemma A and Theorem B are discussed in the previous post. Lemma A is shown to be equivalent to the fundamental theorem of arithmetic. Lemma A makes CRT possible.

Lemma A
Let $a$, $b$ and $d>0$ be integers. Suppose that $\text{GCD}(a,d)=1$, i.e. the greatest common divisor of $a$ and $d$ is 1. If $d \lvert (a \cdot b)$, then $d \lvert b$.

Theorem B
The following conditions are equivalent:

1. The statement of Lemma A.
2. (Euclid’s lemma) If $p$ is a prime number and $p \lvert (a \cdot b)$, then either $p \lvert a$ or $p \lvert b$.
3. Every positive integer $n>1$ can be written as a product of prime numbers and that this product (called a factorization) is unique.

In this post, we start from Lemma A and derive several versions of CRT. First, let’s look at a consequence of Lemma A.

Lemma C
Let $m_1,m_2,\cdots,m_t$ be positive integers that are pairwise relatively prime. Let $M=m_1 \cdot m_2 \cdots m_t$. Then for any integer $n$,

$M \lvert n$ if and only if $m_i \ \lvert \ n$ for each $i$.

Proof
The direction $\rightarrow$ is clear.

We show the direction $\leftarrow$. Suppose that for each $i$, $m_i \lvert n$. Then $n=m_1 \cdot r_1$ for some integer $r_1$. Note that $m_2 \lvert n=m_1 \cdot r_1$. By Lemma 1, $m_2 \lvert r_1$. We can write $n=m_1 \cdot m_2 \cdot r_2$ for some integer $r_2$. Continue the same argument, it follows that $n=m_1 \cdot m_2 \cdots m_t \cdot r$ for some integer $r$. This means that $M \lvert n$. $\square$

____________________________________________________________________________

The Chinese remainder theorem

The following are several statements of the Chinese remainder theorem. The first version is a re-statement of Lemma C using congruence notation.

Theorem D (Chinese Remainder Theorem)
Let $m_1,m_2,\cdots,m_t$ be positive integers that are pairwise relatively prime. Let $M=m_1 \cdot m_2 \cdots m_t$. Then for any integers $a$ and $b$,

$a \equiv b \ (\text{mod} \ M)$ if and only if $a \equiv b \ (\text{mod} \ m_i)$ for each $i$.

The proof of Lemma C would take care of Theorem D. Note that $a \equiv b \ (\text{mod} \ y)$ means that $y \lvert (a-b)$.

Theorem E (Chinese Remainder Theorem)
Let $m_1,m_2,\cdots,m_t$ be positive integers that are pairwise relatively prime. Let $M=m_1 \cdot m_2 \cdots m_t$. Then for any integers $a$ and $b$,

the integer $x_0$ is a solution of the linear congruence equation $a \cdot x \equiv b \ (\text{mod} \ M)$ if and only if the integer $x_0$ is satisfies simultaneously the following linear congruence equations:

$a \cdot x \equiv b \ (\text{mod} \ m_1)$

$a \cdot x \equiv b \ (\text{mod} \ m_2)$

$\cdots$

$a \cdot x \equiv b \ (\text{mod} \ m_t)$

Proof
By Theorem D, $a \cdot x_0 \equiv b \ (\text{mod} \ M)$ if and only if $a \cdot x_0 \equiv b \ (\text{mod} \ m_i)$ for each $i$. $\square$

Theorem F (Chinese Remainder Theorem)
Suppose $m_1,m_2,\cdots,m_t$ are positive integers that are pairwise relatively prime. Let $m=m_1 \cdot m_2 \cdots m_t$. Suppose we have the following system of linear congruence equations

$a_1 \ x \equiv b_1 \ (\text{mod} \ m_1)$

$a_2 \ x \equiv b_2 \ (\text{mod} \ m_2)$

$\cdots$

$a_{t-1} \ x \equiv b_{t-1} \ (\text{mod} \ m_{t-1})$

$a_t \ x \equiv b_t \ (\text{mod} \ m_t)$

such that each of the linear congruence equations has a unique solution, i.e. for each $i$, $a_i$ and $m_i$ are relatively prime. Then the system of linear congruence equations has a unique solution modulo $m=m_1 \cdot m_2 \cdots m_t$.

Proof
First, a solution is produced. Then it is shown that the solution is unique. To produce the solution, the first step is solve each equation individually. Because $a_i$ and $m_i$ are relatively prime, the equation $a_i \ x \equiv b_i \ (\text{mod} \ m_i)$ has a unique solution $c_i$. Thus $a_i \ c_i \equiv b_i \ (\text{mod} \ m_i)$ for each $i$.

Next, let $N_i$ be the product of all the moduli $m_j$ where $j \ne i$. Note that $N_i$ and $m_i$ are still relatively prime. There exists a unique $n_i$ such that $N_i \ n_i \equiv 1 \ (\text{mod} \ m_i)$. In other words, $n_i$ is the multiplicative inverse of $N_i$ modulo $m_i$.

The proposed solution is $x_0=c_1 \cdot N_1 \cdot n_1+c_2 \cdot N_2 \cdot n_2+\cdots+c_t \cdot N_t \cdot n_t$. The following shows that $x_0$ is the solution to each equation.

\displaystyle \begin{aligned} a_i x_0 &\equiv a_i (c_1 \cdot N_1 \cdot n_1+c_2 \cdot N_2 \cdot n_2+\cdots+c_i \cdot N_i \cdot n_i+ \cdots +c_t \cdot N_t \cdot n_t) \\&\equiv a_i \cdot c_1 \cdot N_1 \cdot n_1+a_i \cdot c_2 \cdot N_2 \cdot n_2+\cdots+a_i \cdot c_i \cdot N_i \cdot n_i +\cdots + a_i \cdot c_t \cdot N_t \cdot n_t \\&\equiv a_i \cdot c_i \cdot N_i \cdot n_i \\&\equiv a_i \cdot c_i \\&\equiv b_i \ (\text{mod} \ m_i) \end{aligned}

All the terms containing $N_j$ with $j \ne i$ drop out since $N_j$ contains $m_i$ as a factor. The product $N_i \cdot n_i$ drops out since it is congruent to 1 modulo $m_i$. Then $a_i \cdot c_i$ is congruent to $b_i$ modulo $m_i$.

To show the uniqueness, suppose $x$ is also a solution to the system of linear congruence equations. Then $a_i \ x \equiv a_i \ x_0 \ (\text{mod} \ m_i)$ for each $i$. Multiplying the inverse of $a_i$ on both sides, we have and $x \equiv x_0 \ (\text{mod} \ m_i)$ for each $i$. By Theorem E, $x \equiv x_0 \ (\text{mod} \ m)$. $\square$

Theorem G (Chinese Remainder Theorem)
Suppose $m_1,m_2,\cdots,m_t$ are positive integers that are pairwise relatively prime. Let $m=m_1 \cdot m_2 \cdots m_t$. For any sequence of integers $c_1,c_2,\cdots,c_t$, the following system of linear congruence equations

$x \equiv c_1 \ (\text{mod} \ m_1)$

$x \equiv c_2 \ (\text{mod} \ m_2)$

$\cdots$

$x \equiv c_{t-1} \ (\text{mod} \ m_{t-1})$

$x \equiv c_t \ (\text{mod} \ m_t)$

has a unique solution modulo $m=m_1 \cdot m_2 \cdots m_t$.

Proof
This follows directly from Theorem F. $\square$

____________________________________________________________________________

To complete the loop

To complete the loop, we show that Theorem G implies Theorem D. Suppose that $a \equiv b \ (\text{mod} \ m_i)$ for each $i$. Consider the following system of congruence equations:

$x \equiv b \ (\text{mod} \ m_1)$

$x \equiv b \ (\text{mod} \ m_2)$

$\cdots$

$x \equiv b \ (\text{mod} \ m_t)$

The number $b$ is clearly a solution to this system of equations. By Theorem G, this solution is unique. So any other solution to this system must be congruent to $b$ modulo $m=m_1 \cdot m_2 \cdots m_t$. By assumption, $a$ is a solution to the system. So $a \equiv b \ (\text{mod} \ m)$. $\square$

The loop $D \rightarrow E \rightarrow F \rightarrow G \rightarrow D$ is now complete. Theorem G is the usual statement of CRT. Based on the loop, any one of the theorems can be called the Chinese remainder theorem. Note that the loop by itself does not establish the Chinese remainder theorem. For that to happen, some condition outside the loop must imply one condition in the loop. The above discussion shows that the fundamental theorem of arithmetic (in the form of Lemma A) implies Theorem D.

____________________________________________________________________________

CRT is a versatile tool and is found to be useful in many areas of mathematics. One approach in applying CRT is that of a divide and conquer idea. The original problem is divided into smaller problems, which can be solved independently of one another. At the end, the results of the smaller problems are combined to form the solution of the original problem. For example, in solving a linear congruence equation $a \cdot x \equiv b \ (\text{mod} \ M)$ for a large modulus $M$, CRT in the form of Theorem E suggests that the problem can be broken up into a set of linear congruence equations with smaller moduli. For this reason, CRT is important in computing (both theory and applications), especially in computing intensive areas such as coding theory and cryptography.

In the next posts, we discuss two algorithms for solving CRT simultaneous systems of equations and look at a few applications.

____________________________________________________________________________
$\copyright \ 2015 \text{ by Dan Ma}$

Another look at the fundamental theorem of arithmetic

This is the first post of a series of blog posts on the Chinese remainder theorem, often abbreviated CRT. In this post, we take another look at the fundamental theorem of arithmetic. This post is background for the next post, which will show that CRT can be built step by step from the fundamental theorem of arithmetic.

Links to the other posts in the series:
second post, third post, fourth post.

Every integer can be factored into a product of primes in essentially one way. This fact is called the fundamental theorem of arithmetic. For example, the number 84 is 2 x 2 x 3 x 7. The ordering of the primes is not important here since, for example, 2 x 2 x 3 x 7 is the same as 3 x 2 x 7 x 2. The example of 84 seems to suggest that the fundamental theorem of arithmetic is simply an exercise at the elementary school. In general, factoring a number is a very hard problem. For integers with hundreds or thousands of digits, finding the factors may take more seconds than the number of atoms in the universe! The fundamental theorem of arithmetic guarantees that such factorization exists for any integer, large or small. Because of this, the prime numbers are the building blocks of the integers (the atoms of arithmetic).

What is the importance of knowing that every integer can be factored into prime numbers in a unique way? A short answer is that the fundamental theorem of arithmetic is a foundation result. A vast array of mathematical structures are built on this foundation. The fundamental theorem of arithmetic is the beginning point of many mathematical stories. In this and subsequent posts, we highlight one such example. We show that the Chinese remainder theorem follows from the fundamental theorem of arithmetic. CRT combines beauty and utility. Even though CRT has been known for at least 1,000 years, it continues to present new applications in many areas, e.g. in coding theory, cryptography and the theory of computing. Surprisingly, the proof of CRT is quite simple. CRT follows from a lemma that is equivalent to the fundamental theorem of arithmetic. As a result, the discussion in this and the subsequent posts is a clear demonstration of the power of the fundamental theorem of arithmetic.

In this post, we discuss the fundamental theorem of arithmetic. In the next posts, we discuss CRT.

____________________________________________________________________________

The lemma

The starting point is the following lemma.

Lemma A
Let $a$, $b$ and $d>0$ be integers. Suppose that $\text{GCD}(a,d)=1$, i.e. the greatest common divisor of $a$ and $d$ is 1. If $d \lvert (a \cdot b)$, then $d \lvert b$.

Proof
Suppose that $\text{GCD}(a,d)=1$. By the extended Euclidean algorithm, the linear diophantine equation $ax+dy=1$ is solvable in integers. Let $x$ and $y$ be integers that satisfy this equation. Multiply this equation by $b$ to obtain $abx+dby=b$. Since $d \lvert (a \cdot b)$, $d$ divides both terms on the left hand side of the last equation. Thus $d \lvert b$. $\square$

Lemma A is a simple statement. The proof is also simple, simply using the extended Euclidean algorithm, which is the Euclidean algorithm working backward. the Euclidean alogorithm consists, at heart, of a series of divisions to derive the greatest common divisor. As discussed below, the simple Lemma A leads to the fundamental theorem of arithmetic and Lemma A can also be derived from the fundamental theorem of arithmetic.

____________________________________________________________________________

The fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that any positive integer greater than 1 can be expressed as a product of primes and that the factorization is unique. The theorem is proved in this previous post. Here, we show that it is equivalent to Lemma A.

Theorem B
The following conditions are equivalent:

1. The statement of Lemma A.
2. (Euclid’s lemma) If $p$ is a prime number and $p \lvert (a \cdot b)$, then either $p \lvert a$ or $p \lvert b$.
3. (Fundamental Theorem of Arithmetic) Every positive integer $n>1$ can be written as a product of prime numbers and that this product (called a factorization) is unique.

Condition 2 is usually referred to as the Euclid’s lemma. Condition 3 is, of course, a statement of the fundamental theorem of arithmetic. The story we would like to tell is that Lemma A is equivalent to the fundamental theorem of arithmetic. Thus any consequence of Lemma A is also a consequence of the fundamental theorem of arithmetic.

The proof of $1 \rightarrow 2 \rightarrow 3$ is done in this previous post. We also like to point out one additional argument is needed to establish the equivalence of the three conditions. The proof to establish the fundamental theorem of arithmetic in the previous post uses an induction argument to show that every integer is a product of prime numbers. So condition 2 plus the induction argument establish condition 3. The role of condition 2 is to establish the uniqueness of the product of primes. We only need to show $3 \rightarrow 1$.

Proof
$3 \rightarrow 1$
Suppose that $a$ and $d$ have no prime factors in common and that $d \lvert (a \cdot b)$. So we have $a \cdot b=d \cdot m$ for some integer $m$. By condition 3, we can express $a$ and $d$ as a product of primes as follows:

$\displaystyle p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_t^{\alpha_t} \times b=q_1^{\delta_1} \cdot q_2^{\delta_2} \cdots q_r^{\delta_r} \times m$

The numbers $p_i$ are the prime factors of $a$ and the numbers $q_i$ are the prime factors of $d$. The exponents $\alpha_i$ and $\delta_j$ are positive integers. Note that $p_i \ne q_j$ for any $i$ and $j$. Each $q_i^{\delta_i}$ must appear in the prime factorization of the left-hand side. Since $q_i^{\delta_i}$ cannot appear in the factorization of $a$, it must be in the factorization of $b$. $\square$

The loop $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ shows the equivalence of the three statements. From a logical standpoint, any one of these statements is the fundamental theorem of arithmetic. As a demonstration of the power of the fundamental theorem of arithmetic, the next post shows that the Chinese remainder theorem is derived using Lemma A.

____________________________________________________________________________
$\copyright \ 2015 \text{ by Dan Ma}$