The Chinese Remainder Theorem

At the time the greatest common divisor was defined, it would have been possible to define a related number, the least common multiple.

Definition 5.1.  Suppose a and b are two positive integers.  The least common multiple [a, b] is the smallest positive integer which is a multiple of both a and b.  The relationship between them is illustrated in the following lemma.

Lemma 5.2.  Let a and b be two positive integers.  Then

a)  (a, b) [a, b] = ab
b)  If d | a and d | b, then d | (a, b)
c)  If a | m and b | m, then ab | m.

a)  Consider the prime factorizations of a, b.  Let

a = p₁^a1p₂^a2...p_k^ak
b = p₁^b1p₂^b2...p_k^bk

(in this case, some exponents may be 0; a prime is included in the list if it is a divisor of either a or b).

Then

(a, b) = p₁^c1...p_k^ck where c_i = min {a_i, b_i)
[a, b] = p₁^d1...p_k^dk where d_i = max (a_i, b_i)

Since a_i + b_i= c_i + d_i for each i, (a, b) [a, b] = ab.

b)  There are integers s, t such that (a, b) = as + bt.  If a = dx, b = dy, (a, b) = d(xs) + d(yt) = d(xs + yt).  So d | (a, b).

c)  Let m = [a, b]q + r, 0r<[a, b].  As in b), since a | m and a | [a, b], a | r.  Similarly b | r.  Since r < [a, b], this contradicts the fact that [a, b] is the LEAST common multiple of a and b.  So r = 0.  If (a, b) = 1, [a, b] = ab by part a), so ab | m.

4/15 + 5/21 = (4/15)((21/3)/(21/3)) + (5/21)((21/3)/(21/3)) = (4(7) + 5(5))/105 = 53/105.

Theorem 5.3.  The Chinese Remainder Theorem  Let m1, m2, ..., mr be positive integers such that (mi, mj) = 1 if ij.  Let a1, ..., ar be any integers.  Then the system of congruences xa1 (mod m1) xa2 (mod m2) .... xar (mod mr) has a common solution of x, and if x, y are two such solutions xy(mod m=m1m2...mr).  Proof: For each j, let kj = m / mj.  Thus (kj, mj) = 1, since mj has no factors in common with any mi if ij.  Thus there is an integer bj with kjbj11(mod mj).  Also, if ij kjbj10(mod mi).  Let x = Skjbjaj 1  j  r.  Then, for each i, xkibiai1ai (mod mi).  Further, if x and y are two solutions xy(mod mi).  Thus mi | (x - y) for each i.  By Lemma 5.2c) m | (x - y).  So xy(mod m). Here is a classic example.  A man has a basket of eggs.  He doesn't know how many eggs there are, but when he counts them by twos, there is one left over.  Similarly, when he counts by threes or fives, there is one remaining.  When he counts by sevens, there are two left over.  What is the least number of eggs he could have in his basket?  If x is the number of eggs, the system of congruences is x1(mod 2) x1(mod 3) x1(mod 5) x2(mod 7) So m=210, k1=105, k2=70, k3=42, k=30.  To find b1, b2, b3, b4 solve  105b111(mod 2) or b111(mod 2)   70b211(mod 3) or b211(mod 3)   42b311(mod 5) or 2b311(mod 5)   30b411(mod 7) or 2b411(mod 7) One set of solution is b1=1, b2=1, b3=3, b4=4.  Thus x=105(1)(1)+70(1)(1)+42(3)(1)+30(4)(1)=541.  The smallest positive integer congruent to 541(mod 210) is 121.  Thus the least number of eggs the man has is 121.

While computations such as those of the above example are fascinating, the theoretical consequences are more important.

Theorem 5.4.  Suppose (m₁, m₂) = 1.  Then the equation f(x)0(mod m=m₁m₂) has a solution if and only if both f(x)0(mod m₁), and f(x)0(mod m₂) have solutions (here f(x) is a polynomial with integer coefficients).

Remark:  In fact if f(x)0(mod m₁) has n₁ solutions and f(x)0(mod m₂) has n₂ solutions, then f(x)0(mod m) has n₁n₂ solutions.  See Niven, Zuckerman, and Montgomery, Theorem 2.20, for a proof.  In the book, the theorem will be used to see if x²1 a has solutions for certain composite moduli.

Proof:  If f(x)0(mod m), then for some integer k, f(x)km=km₁m₂.  Thus f(x)0(mod m₁) and f(x)0(mod m₂).  On the other hand, suppose f(x)0(mod m₁) and f(x)0(mod m₂) both have solutions.  Suppose f(a₁)0(mod m₁) and f(a₂)(mod m₂).  By the Chinese Remainder Theorem, there is an integer x (mod m), xa₁(mod m₁) and xa₂(mod m₂).  Then f(x)f(a₁)0(mod m₁) and f(x)f(a₂)0(mod m₂).  Thus m₁ | f(x), m₂ | f(x).  Thus since (m₁, m₂)1, by Lemma 5.2 m=m₁m₂ | f(x), so f(x)0(mod m).

The Chinese Remainder Theorem can also be used to help calculate the value of Euler's -function.

Theorem 5.5.

a)  If p is a prime, (pⁿ) = pⁿ - p^n-1
b)  If (m₁, m₂) = 1, (m₁, m₂) = (m₁)(m₂).

a)  Suppose p is a prime.  Then, consider the complete residue system 1, 2, ..., pⁿ.  The only integers in this list NOT relatively prime to p are p₁, 2p, ..., (p^n-1)p.  Thus (pⁿ) = pⁿ - p^n-1.
b)  The goal is to establish a one-to-one correspondence between integers a in the set {1, 2, ..., m} which are relatively prime to m and pairs of integers (a₁, a₂), where

a₁ is in {1, 2, ..., m₁}, relatively prime to m₁
a₂ is in {1, 2, ..., m₂}, relatively prime to m₂.

First, suppose (a, m) = 1.  Then (a, m₁) = 1 and (a, m₂) = 1.  Let a_i be the remainder when a is divided by m_i, _i = 1, 2.  Second, suppose a₁, a₂ are as above.  Then the Chinese Remainder Theorem assures there is a unique a in {1, 2, ..., m} with aa₁(mod m₁) and aa₂(mod m₂).  Since (a, m₁) = 1 and (a, m₂) = 1, it follows that (a, m₁m₂) = 1.  Thus, since this one-to-one correspondence exists, f(m) = f(m₁) f(m₂).

For example, since (4) = 4 - 2 = 2 and (5) = 4, (20) = 8.  Since (8) = 8 - 4 = 4 and (9) = 9 - 3 = 6, (72) = 4(6) = 24.  One of the pairings of part b) of the theorem is of (1, 2), where (1, 8) = 1 and (2, 9) = 1 with 65, a number relatively prime to 72 with 651(mod 8) and 652(mod 9).  This is the solution of the system

x1(mod 8)
x2(mod 9)

determined by the Chinese Remainder Theorem (k₁=9, k₂=8; b₁=1, b₂=8) since x9(1)(1) + 8(8)(2)=13765(mod 72).

Binary Quadratic Forms

In order to find which integers are of the form x² + xy + y² for integers x, y (as desired by Loeb and Dacey), it is first necessary to study binary quadratic forms in general.

Definition 5.6.

a)  A function f(x, y) = ax² + bxy +cy² is called a binary quadratic form.  If n = f(x₀, y₀) for some integers x₀, y₀, then the form f represents n properly if (x₀, y₀) = 1, improperly if (x₀, y₀) 1.
b)  The points (x, y) where x, y are integers are called lattice points.
c)  The discriminant d of a quadratic form is d = b² - 4ac.
d)  A form is called

positive definite if it takes on only positive values when (x, y) (0, 0).
negative definite if it takes on only negative values when (x, y) (0, 0).
semidefinite if it takes on only non-negative values or non-positive values.

a) d0 or 1 (mod 4)
b)  A form with d = 0 is semidefinite but not definite.  A form with positive discriminant is indefinite.  A form with negative discriminant is definite (positive if a>0, negative if a<0)

Definition 5.9.  Two quadratic forms f(x, y) = ax² + bxy + cy² and g(x, y) = Ax² + Bxy + Cy² are said to be equivalent if there is a matrix M of determinant 1, M = [m₁₁, m₁₂; m₂₁, m₂₂], such that g(x, y) = f(m₁₁x + m₁₂y, m₂₁x + m₂₂y).

Theorem 5.8 suggests that matrices of determinant -1 could have been allowed in Definition 5.9.  Indeed, some number theory texts allow this.  Still others use the term "properly equivalent" if det M = 1, "improperly equivalent" if det M = -1.  Niven, Zuckerman, and Montgomery use the approach of Definition 5.9.

Theorem 5.9.

a)  Equivalence of forms partitions the set of quadratic forms into sets of forms all of which are equivalent to each other.
b)  Equivalent forms represent the same integers n, and represent the same integers properly.
c)  Equivalent forms have the same discriminant.

Definition 5.10.  Let f be a binary quadratic form whose discriminant is not a perfect square; f is called reduced if  -|a| < b |a| < |c| or if 0 b |a| = |c|.

Theorem 5.11.  If d is not a perfect square, each equivalence class of binary quadratic forms of discriminant d contains at least one reduced form.

Theorem 5.12.  Suppose f is a reduced positive definite quadratic form of discriminant d.  The 0 < a (-d/3)^0.5 .

Corollary 5.13.  There is only one reduced form with discriminant -3.
 

Proof:  By Theorem 5.12 a = 1; b = 0 is impossible since db² (mod 4).  Therefore, Definition 5.10 assures b = 1, c = 1.

Theorem 5.14.  Let n and d be given integers with n0.  There is a binary quadratic form of discriminant d which represents n properly if and only if x²1d(mod 4|n|) has a solution.

Corollary 5.15.  Suppose d 0 or 1 (mod 4).  If p is an odd prime, there is a binary quadratic form of discriminant which represents p if and only if (d/p) = 1.

Application to Löschian Numbers

Definition 5.16. A positive integer n is called Löschian if there are integers x and y such that n = x² + xy + y².

Since there is only one reduced form of discriminant -3, namely x² + xy + y², and since if n is representable by a form of discriminant -3 if and only if it is representable by an equivalent reduced form, Theorem 5.14 assures that n is properly representable by x² + xy + y² if and only if x²1 -3 (mod 4n) or x² + 3  0(mod 4n) has a solution.

By Theorem 5.4, x² +3  0 (mod 4n) has a solution if and only if x² +3  0 (mod p_i^ai) has a solution for every i.

1)  If p | n and p 1 (mod 3), then by quadratic reciprocity (-3/p) = (p/3) = 1 and also (-3/pⁿ) = (pⁿ/3) = (p/3)ⁿ = 1, so x² +3  0(mod pⁿ) has a solution for every n.
2)  However suppose p2(mod 3).  Then (-3/p) = 1, and so x² +3  0(mod p) has no solution.  But x² +30(mod pⁿ) implies pⁿ | (x² +3) which in turn implies that p | (x² +3), which is impossible.
3)  Of course x² +30(mod 3) has a solution (x = 0) but x² +30(mod 3ⁿ) has no solution for n>1 since 9|(x² +3) implies 3|x² implies 3|x, say x=3a; but then x² +3 = 3(3a² + 1)3 (mod 9), a contradiction.

Thus N is properly representable by x² + xy + y² if and only if N = 3^app^b, where every p1(mod 3) and a =0 or 1.  Of course if N = x² + xy + y² , c²N = (cx)² + (cx)(cy) + (cy)² so the square of any properly representable integer is improperly representable.  Thus an integer N is Löschian if and only if N = 3^app^bpq^2g where every p1(mod 3), every q 2(mod 3).  Of course, sometimes, it is not necessary to find the prime factorization of N to see if it is Löschian.  Since always x² + xy + y²1 0 or 1 (mod 3) [try the nine cases xa, yb (mod 3); if a = b, x² + xy + y²1 0(mod 3); otherwise x² + xy + y²1 1(mod 3) ].

So if N2(mod 3), N is non-Löschian.

For example, N=32759 is non-Löschian (it is not immediately obvious that N = 17(41)(47).

Similarly, suppose N = pⁿM, where (M, p) = 1, p0, 1 (mod p).  If M2(mod 3), N is non-Löschian, since the sum of the exponents of the primes 2(mod 3) in the prime factorization of M must be odd.

For example, N = 8073 = 3³(299), and 299 2 (mod 3).  So 8073 is non-Löschian.  In fact, 8073 = 3³(13)(23).

In summary,
Theorem 5.17.  Let N be a positive integer.  Then

a)  N is properly representable as x² + xy + y² for integers x, y if and only if N = 3^aM, where a = 0,1 and every prime factor of M is  1(mod 3).
b)  N is Löschian if N = 3^aMT², where every prime factor of M is  1(mod 3) and every prime factor of T is  2(mod 3).
c)  N is non-Löschian if N2(mod 3)
d)  N is non-Löschian if N = pⁿM, (M, p) = 1, M2(mod 3).

• K =  175 is Löschian, since K = 52 x 7.
• K = 125 = 5³ is not Löschian
• K = 245 = 5 x 72 is not Löschian
• K = 85 is not Löschian, even though 85 is congruent to 1(mod 3), since K = 5 x 17, and both 5 and 17 are congruent to 2(mod 3)
• K = 49 is Löschian as 49 may be generated using the Diophantine equation on either the ordered pair (0, 7) or on (3, 5):  representation is not unique.