Crt - Homework assignment 2020-students PDF

Preview

Summary

Homework assignment 2020-students...

Description

Multiple Congruences and Linear Diophantine Equations Problem. According to a Dutch legend, in the year 1645, a group of 35 pirates found a chest containing a fabulous treasure, consisting of valuable golden coins. They tried to divide the treasure into equal parts, but 22 coins were left over. A vicious fight erupted, which resulted in the death of 13 pirates. The remaining pirates placed all coins back into the chest, and attempted a second partition. This time 19 coins left over. They became as enraged as before, with 8 more pirates dying in the ensuing fight. After that the survivors were exhausted, so when they split the original treasure one last time, nobody went near the 1 coin left over. In 1998 historians from the University of Regina were able to determine all possible values for the number of coins in the chest. How did they do it? Solution. Let N stand for the number of coins in the chest. Then N is of the from N = 22 + 35a,

N = 19 + 22b,

N = 1 + 14c,

for some integers a, b, c ≥ 0. We can easily make a list of possible values for N satisfying each of these conditions individually. LIST A:

22, 57, 92, 127, ....................

jumps by 35

LIST B:

19, 51, 73, 95, ......................

jumps by 22

LIST C:

1, 15, 29, 43, ........................

jumps by 14

We look for all numbers, if any, common to these three lists. Mere inspection of the lists does not seem to produce even a single common number. A fruitful idea might be to first try to find a number common to just 2 lists, say lists B and C. Starting at 1, how many jumps of 14 will produce a number in list B? We look for X ≥ 0 (the number of jumps of 14) such that 1 + 14X is on list B, that is 1 + 14X = 19 + 22Z, for some integer Z ≥ 0. Letting Y = −Z, we can rewrite the above equation as 14X + 22Y = 18. 1

This is an example of a linear Diophantine equation. We can re-write our equation as 2 × (7X + 11Y ) = 2 × 9, which is equivalent to 7X + 11Y = 9.

(1)

The ancient Greeks found a method to find a solution to 7X + 11Y = 1, which then produces a solution to (1) through multiplication by 9. The Greek method is based on the following observation: call the expression 7X + 11Y a linear combination of 7 and 11. Divide 11 into 7 to get 11 = 1 × 7 + 4. They realized that any linear combination of 7 and 4 can be reconstructed to look like a linear combination of 7 and 11 (and conversely). A repeated application of this idea eventually yields the desired information. In our case, 11 = 1 × 7 + 4, 7 = 1 × 4 + 3, 4 = 1 × 3 + 1. Reading these equations backwards yields 1 = 1 × 4 + (−1) × 3 = 1 × 4 + (−1)[7 + (−1) × 4] = 2 × 4 + (−1) × 7, so 1 = 2 × [11 + (−1) × 7] + (−1) × 7 = 2 × 11 + (−3) × 7. Multiplying by 9 yields 9 = (−27) × 7 + 18 × 11. This gives one solution to (1), but not of the desired form, since we are looking for a positive number of jumps. Well, given our solution, we can easily produce others, as follows (it can be shown that any solution to (1) can be produced by this shifting process): 9 = (−27 + 3 × 11) × 7 + (18 − 3 × 7) × 11, that is 9 = 6 × 7 + (−3) × 11. 2

Thus, X = 6 is the smallest jump of 14 that will produce a number in list B. Which number? Well, 1 + 6 × 14 = 85, which is the first number common to lists B and C. Clearly 85 is not in list A, so we need to produce all numbers common to lists B and C, to search for the first one that lands in list A. Well, lists B and C jump by 22 and 14, respectively, and they have a first common point at 85. To reach another common point, we must make a jump that is a multiple of 22 and 14 at the same time. The smallest common multiple of 22 = 2 × 11 and 14 = 2 × 7 is 2 × 11 × 7 = 154. Thus, the second number common to lists B and C will be 85 + 154 = 239, and we see that the list of all numbers common to lists B and C, is LIST BC:

85, 85 + 154, 85 + 2 × 154, ........................

jumps by 154

Which of these numbers, if any, also appear in list A? As above, we need to find how many jumps X of 154 will make 85 + 154X be in list A, that is, of the form 22 + 35Z for some Z ≥ 0. As before, letting Y = −Z, we are lead to the equation 154X + 35Y = −63. Removing a common factor of 7, this turns out to be equivalent to 22X + 5Y = −9. We now use the Greek method of repeated division to find a solution to 22X + 5Y = 1. We then scale by -9 to get a solution to 22X + 5Y = −9, and finally shift this solution to see that the smallest possible jump of 154 we seek is by X = 3 (with Y = −15). This produces the smallest number common to all lists, namely 85 + 3 × 154 = 547. Now, lists A, B and C jump by 35, 22 and 14, respectively and have their first common point at 547. The next common point will be obtained by a jump that is a multiple 35, 22 and 14 at the same time. The smallest common multiple of 35, 22, 14 is 2×5×7×11 = 770. Thus, the second number common to lists A, B and C will be 547 + 770 = 1317, and we see that the list of all numbers common to lists A, B and C, is LIST ABC:

547, 547+770, 547+2×770, ........................

3

jumps by 770

In terms of congruences, what we did was to solve the multiple congruence equations N ≡ 22

mod 35, N ≡ 19

mod 22, N ≡ 1

mod 14.

Let us work out this problem again using congruences. From the third equation we see that N = 1 + 14a for some a ∈ Z. We want to find all N = 1 + 14a that satisfy the second equation, so we look for all a such that 1 + 14a ≡ 19 mod 22, that is 14a ≡ 18 mod 22. This is a congruence equation whose associated linear diophantine equation is 14a + 22b = 18. Dividing through by gcd(14, 22) = 2 we obtain the reduced linear diophantine equation equation 7a + 11b = 9. We first solve 7a +11b = 1. By inspection we see that 7 × (−3) +11 × 2 = 1. Multiplying through by 9 we obtain 7 × (−27) +11× 18 = 9. The general solution to 7a + 11b = 9 is a = −27 + 11k, b = 18 − 7k, k ∈ Z. Thus a ≡ −27 ≡ −5 ≡ 6 mod 11, so a = 6 + 11k for some k ∈ Z. Replacing this in N = 1 + 14a we get N = 1 + 14(6 + 11k) = 85 + 154k for some k ∈ Z. We now repeat the above argument. That is, we want to find all N = 85 + 154k that satisfy the third equation, so we look for all k such that 85 + 154k ≡ 22 mod 35, that is 14k ≡ −63 ≡ 7 mod 35. This is a congruence equation whose associated linear diophantine equation is 14k + 35ℓ = 7. Dividing through by gcd(7, 35) = 7 we obtain the reduced linear diophantine equation equation 2k + 5ℓ = 1. By inspection we see that 2 × (−2) + 5 × 1 = 1. The general solution to 2k + 5ℓ = 1 is k = −2 + 5t, ℓ = 1 − 2t, t ∈ Z. Thus k ≡ −2 ≡ 3 mod 5, so k = 3 + 5t for some t ∈ Z. Replacing this in N = 85 + 154k we get N = 85 + 154(3 + 5t) = 547 + 770t for some t ∈ Z. This general solution is exactly the same as the one found above. Question. Let m1 , m2 , ..., ms and a1 , a2 , ..., as be given integers. What are the exact conditions on m1 , m2 , ..., ms and a1 , a2 , ..., as that ensure the existence of a solution to the multiple congruence equations N ≡ a1

mod m1 , N ≡ a2

mod m2 , . . . , N ≡ as

mod ms .

I claim a necessary condition is that ai ≡ aj mod gcd(mi , mj ) for all 1 ≤ i, j ≤ s. Indeed, suppose the above equations have a solution N . Then N satisfies the ith and j th equations N ≡ ai

mod mi , and N ≡ aj 4

mod mj .

Since gcd(mi , mj ) is a factor of both mi and mj , we deduce. N ≡ ai

mod gcd(mi , mj ), and N ≡ aj

mod gcd(mi , mj ).

Thus ai ≡ N ≡ aj mod gcd(mi , mj ), so ai ≡ aj mod gcd(mi , mj ) as claimed. As an illustration, the multiple congruence equations N ≡3

mod 6, N ≡ 2

mod 8

have no solution because gcd(6, 8) = 2 does not divide 3 − 2 = 1. In fact, the numbers satisfying the second equation are even and those satisfying the first equation are odd, so we can also see directly that there are no solutions. It can be shown (see Exercise 1 below) that the condition ai ≡ aj mod gcd(mi , mj ) for all 1 ≤ i, j ≤ s is also sufficient for the existence a solution to N ≡ a1

mod m1 , N ≡ a2

mod m2 , . . . , N ≡ as

mod ms .

In particular, if m1 , . . . , ms are pairwise relative prime, there is always a solution to the above equation. It is easy to see that that any two solutions N1 , N2 must satisfy N1 ≡ N2 mod lcm(m1 , . . . , ms ). Indeed, we have N1 ≡ a1 ≡ N2

mod m1 , N1 ≡ a2 ≡ N2

mod m2 , . . . , N1 ≡ as ≡ N2

mod ms ,

so N1 ≡ N2

mod m1 , N1 ≡ N2

mod m2 , . . . , N1 ≡ N2

mod ms .

This says that N1 −N2 is a multiple of m1 , . . . , ms , so N1 −N2 is a multiple of lcm(m1 , . . . , ms ), as claimed. Exercise 1. Suppose a1 ≡ a2 mod gcd(m1 , m2 ). Show that there is an integer N such that N ≡ a1

mod m1 , N ≡ a2

mod m2 .

Hint: Translate it into the problem of solving a linear diophantine equation.

5...