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] = abProof:
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. LetThe least common multiple is used in arithmetic to add fractions, where it is called the least common denominator. For example, since [15, 21] = 15(21)/(15,21) = 15(21)/3 = 105a = p_{1}^{a1}p_{2}^{a2}...p_{k}^{ak}(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).
b = p_{1}^{b1}p_{2}^{b2}...p_{k}^{bk}Then
(a, b) = p_{1}^{c1}...p_{k}^{ck} where c_{i}_{ }= min {a_{i}, b_{i})Since a_{i} + b_{i}= c_{i} + d_{i} for each i, (a, b) [a, b] = ab.
[a, b] = p_{1}^{d1}...p_{k}^{dk} where d_{i}_{ }= max (a_{i}, b_{i})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.
The least common multiple arises when it is desired to solve several congruences (with different moduli) simultaneously. The process below appears to have been known in first century China. Hence it has come to be known as the Chinese Remainder Theorem.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 m_{1}, m_{2}, ..., m_{r }be positive integers such that (m_{i}, m_{j}) = 1 if ij. Let a_{1}, ..., a_{r} be any integers. Then the system of congruences has a common solution of x, and if x, y are two such solutions xy(mod m=m_{1}m_{2}...m_{r}).xa_{1} (mod m_{1}) Proof:
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)So m=210, k_{1}=105, k_{2}=70, k_{3}=42, k=30. To find b_{1}, b_{2}, b_{3}, b_{4} solve 105b_{1}11(mod 2) or b_{1}11(mod 2)One set of solution is b_{1}=1, b_{2}=1, b_{3}=3, b_{4}=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_{1}, m_{2}) = 1. Then the equation f(x)0(mod m=m_{1}m_{2}) has a solution if and only if both f(x)0(mod m_{1}), and f(x)0(mod m_{2}) have solutions (here f(x) is a polynomial with integer coefficients).
Remark: In fact if f(x)0(mod m_{1}) has n_{1} solutions and f(x)0(mod m_{2}) has n_{2} solutions, then f(x)0(mod m) has n_{1}n_{2 }solutions. See Niven, Zuckerman, and Montgomery, Theorem 2.20, for a proof. In the book, the theorem will be used to see if x^{2}1 a has solutions for certain composite moduli.
Proof: If f(x)0(mod m), then for some integer k, f(x)km=km_{1}m_{2}. Thus f(x)0(mod m_{1}) and f(x)0(mod m_{2}). On the other hand, suppose f(x)0(mod m_{1}) and f(x)0(mod m_{2}) both have solutions. Suppose f(a_{1})0(mod m_{1}) and f(a_{2})(mod m_{2}). By the Chinese Remainder Theorem, there is an integer x (mod m), xa_{1}(mod m_{1}) and xa_{2}(mod m_{2}). Then f(x)f(a_{1})0(mod m_{1}) and f(x)f(a_{2})0(mod m_{2}). Thus m_{1} | f(x), m_{2} | f(x). Thus since (m_{1}, m_{2})1, by Lemma 5.2 m=m_{1}m_{2} | 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.
a) If p is a prime, (p^{n}) = p^{n} - p^{n}^{-1}Proof:
b) If (m_{1}, m_{2}) = 1, (m_{1}, m_{2}) = (m_{1})(m_{2}).
a) Suppose p is a prime. Then, consider the complete residue system 1, 2, ..., p^{n}. The only integers in this list NOT relatively prime to p are p_{1}, 2p, ..., (p^{n}^{-1})p. Thus (p^{n}) = p^{n} - p^{n}^{-1}.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
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_{1}, a_{2}), wherea_{1} is in {1, 2, ..., m_{1}}, relatively prime to m_{1}First, suppose (a, m) = 1. Then (a, m_{1}) = 1 and (a, m_{2}) = 1. Let a_{i} be the remainder when a is divided by m_{i}, _{i} = 1, 2. Second, suppose a_{1}, a_{2} are as above. Then the Chinese Remainder Theorem assures there is a unique a in {1, 2, ..., m} with aa_{1}(mod m_{1}) and aa_{2}(mod m_{2}). Since (a, m_{1}) = 1 and (a, m_{2}) = 1, it follows that (a, m_{1}m_{2}) = 1. Thus, since this one-to-one correspondence exists, f(m) = f(m_{1}) f(m_{2}).
a_{2} is in {1, 2, ..., m_{2}}, relatively prime to m_{2}.
determined by the Chinese Remainder Theorem (k_{1}=9, k_{2}=8; b_{1}=1, b_{2}=8) since x9(1)(1) + 8(8)(2)=13765(mod 72).x1(mod 8)
x2(mod 9)
In order to find which integers are of the form x^{2} + xy + y^{2 }for integers x, y (as desired by Loeb and Dacey), it is first necessary to study binary quadratic forms in general.
a) A function f(x, y) = ax^{2} + bxy +cy^{2} is called a binary quadratic form. If n = f(x_{0}, y_{0}) for some integers x_{0}, y_{0}, then the form f represents n properly if (x_{0}, y_{0}) = 1, improperly if (x_{0}, y_{0}) 1.Theorem 5.7.
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^{2} - 4ac.
d) A form is calledpositive 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)Theorem 5.8. Let M = [m_{11}m_{12}; m_{21}, m_{22}]. Let [u; v] = M[x; y], that is u = m_{11}x + m_{12}y, v = m_{21}x + m_{12}y. Then this transformation is a permutation of the lattice points in the plane if and only if det M = +/- 1.
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^{2} + bxy + cy^{2 }and g(x, y) = Ax^{2} + Bxy + Cy^{2} are said to be equivalent if there is a matrix M of determinant 1, M = [m_{11}, m_{12}; m_{21}, m_{22}], such that g(x, y) = f(m_{11}x + m_{12}y, m_{21}x + m_{22}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.
a) Equivalence of forms partitions the set of quadratic forms into sets of forms all of which are equivalent to each other.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|.
b) Equivalent forms represent the same integers n, and represent the same integers properly.
c) Equivalent forms have the same discriminant.
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^{2} (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^{2}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^{2} + xy + y^{2}.
Since there is only one reduced form of discriminant -3, namely x^{2} + xy + y^{2}, 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^{2} + xy + y^{2} if and only if x^{2}1 -3 (mod 4n) or x^{2} + 3 0(mod 4n) has a solution.
By Theorem 5.4, x^{2} +3 0 (mod 4n) has a solution if and only if x^{2} +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^{n}) = (p^{n}/3) = (p/3)^{n} = 1, so x^{2} +3 0(mod p^{n}) has a solution for every n.Thus N is properly representable by x^{2} + xy + y^{2} if and only if N = 3^{a}pp^{b}, where every p1(mod 3) and a =0 or 1. Of course if N = x^{2} + xy + y^{2} , c^{2}N = (cx)^{2} + (cx)(cy) + (cy)^{2} so the square of any properly representable integer is improperly representable. Thus an integer N is Löschian if and only if N = 3^{a}pp^{b}pq^{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^{2} + xy + y^{2}1 0 or 1 (mod 3) [try the nine cases xa, yb (mod 3); if a = b, x^{2} + xy + y^{2}1 0(mod 3); otherwise x^{2} + xy + y^{2}1 1(mod 3) ].
2) However suppose p2(mod 3). Then (-3/p) = 1, and so x^{2} +3 0(mod p) has no solution. But x^{2} +30(mod p^{n}) implies p^{n} | (x^{2} +3) which in turn implies that p | (x^{2} +3), which is impossible.
3) Of course x^{2} +30(mod 3) has a solution (x = 0) but x^{2} +30(mod 3^{n}) has no solution for n>1 since 9|(x^{2} +3) implies 3|x^{2} implies 3|x, say x=3a; but then x^{2} +3 = 3(3a^{2} + 1)3 (mod 9), a contradiction.
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^{n}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^{3}(299), and 299 2 (mod 3). So 8073 is non-Löschian. In fact, 8073 = 3^{3}(13)(23).
In summary,
Theorem
5.17. Let N be a positive integer. Then
a) N is properly representable as x^{2} + xy + y^{2} for integers x, y if and only if N = 3^{a}M, where a = 0,1 and every prime factor of M is 1(mod 3).Löschian numbers: examples of Theorem usage
b) N is Löschian if N = 3^{a}MT^{2}, 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^{n}M, (M, p) = 1, M2(mod 3).