Chapter 4

[About Thomas Hobbes:] He was 40 years old before he looked on geometry; which happened accidentally. Being in a gentleman’s library, Euclid’s Elements lay open, and ”twas the 47 El. libri I” [Pythagoras’ Theorem]. He read the proposition ”By God”, sayd he, ”this is impossible:” So he reads the demonstration of it, which referred him back to such a proposition; which proposition he read. That referred him back to another, which he also read. Et sic deinceps, that at last he was demonstratively convinced of that trueth. This made him in love with geometry.

-John Aubry

4.1 Pythagorean Triples: A Pythagorean triple is a set of positive integers, a, b, c, satisfying a^{2} + b^{2} = c^{2}. That is, they are integers which could be the lengths of the sides of a right-angled triangle. A Pythagorean triple is called primitive if gcd(a, b, c) = 1.

Theorem 4.1.1: If (a, b, c) is a Primitive Pythagorean Triple (hereinafter, PPT), then a and b have different parity. Moreover, each pair from (a, b, c) are relatively prime.

Proof: By contradiction. Assume that a^{2} + b^{2} = c^{2} and gcd(a, b, c) = 1. We will first show that a and b have different parity.

Assume a, b both even. Then a = 2k, b = 2l, for some k, l. So 2 divides a and b, which is a contradiction.

Now assume that a and b are both odd. Then a = 2k + 1, b = 2l + 1, for some k, l. This means that a^{2} = 4k + 1, b^{2} = 4l + 1 for some (different) k, l. So a^{2} + b^{2} is of the form 4k + 2. But this cannot be a perfect square, so we have a contradiction. Since a and b are neither both even nor both odd, therefore, they must have different parity.

Next we will show that no two of (a, b, c) have a common divisor greater than 1, again by contradiction. Assume a, b not relatively prime. Then there is some p > 1 which divides a and b. Now, p^{2} divides a^{2} and b^{2}, so it divides c^{2}. Therefore p must divide c, which is a contradiction, since gcd(a, b, c) = 1. Similarly, we can write a^{2} = c^{2} − b^{2} and b^{2} = c^{2} − a^{2}. If b and c or a and c are not relatively prime, then they have a common divisor, whose square divides the difference of their squares, and thus which divides a or b, respectively, creating a contradiction, since gcd(a, b, c) = 1.

Example 4.1.1: The following table lists a few examples of PPT’s. Note that columns are organized by the difference between b and c.

(3, 4, 5) (8, 15, 17) (20, 21, 29)
(5, 12, 13) (7, 24, 25)

(12, 35, 37)

Notice that since a^{2} + b^{2} = c^{2}, and a^{2} = 1 + 3 + 5+… +n, and c^{2} = 1 + 3 + 5+… +n + (n + 2)+… +(n + m), it follows that b^{2} = 1 + 3 + 5+… +k = (n + 2) + (n + 4)+… (n + m).

Comment: So we can look for Pythagorean triples by checking perfect squares to see if they are equal to the sum of some string of consecutive odds. Whenever we find such a square, it is b^{2}, the sum of the odds from 1 to the end of this string is c^{2}, and their difference is a^{2}.

Theorem 4.1.2: Every Pythagorean Triple is of the form (x, \frac{x^{2}}{2n} − \frac{n}{2}, \frac{x^{2}}{2n} + \frac{n}{2}).

Proof: This is just a formalization of the Comment. Since b and c must differ by some number n, any Pythagorean triple must fit this form.

Conversely, x^{2} + (\frac{x^{2}}{2n} − \frac{n}{2})^{2} = x^{2} + \frac{x^{4}}{4n^{2}} − \frac{x^{2}}{2} + \frac{n^{2}}{4} = (\frac{x^{2}}{2n} + \frac{n}{2})^{2}.

Notice that in our table so far, b and c do not differ by an odd prime. This leads us to the following conjecture:

Theorem 4.1.3: There is no primitive Pythagorean triple (a, b, c) such that b and c differ by an odd prime.

Proof: Suppose that c = b − p, for p and odd prime. Then from Theorem 4.1.2, b = \frac{x^{2}}{2p} − \frac{p}{2} and c = \frac{x^{2}}{2p} + \frac{p}{2} for some x. Now, b must be an integer, so \frac{x^{2}}{p} − p must be an integer, i.e. \frac{x^{2}}{p} is an integer. So p|x^{2}, meaning that p must divide x, since p is prime. But a = x, so then p divides a, and consequently gcd(a, b, c) is not equal to 1. Thus, (a, b, c) is not primitive.

Theorem 4.1.4: The triple (a, b, c) is a primitive Pythagorean triple if and only if a = m^{2} − n^{2}, b = 2mn, and c = m^{2} + n^{2} for some m, n such that gcd(m, n) = 1, (m + n) is odd, and m > n.

Proof: Note that (m^{2} − n^{2})^{2} + (2mn)^{2} = m^{4} − 2m^{2}n^{2} + n^{4} + 4m^{2}n^{2} = (m^{2} + n^{2})^{2} = c^{2}, so (a, b, c) is a Pythagorean triple.

Next we must show that gcd(a, b, c) = 1. Clearly, since gcd(m, n) = 1, gcd(a, b) = gcd(b, c) = 1. But does gcd(a, c) = 1?

Suppose not. Then there is some k which divides both m^{2} −n^{2} and m^{2} +n^{2}. Adding these together, we see that k|2m^{2}. So k = 2 or k|m. But m and n have different parity, so m^{2} − n^{2} and m^{2} + n^{2} are both odd, and so k cannot be 2. Therefore k|m, but this is a contradiction, since then k would divide n, and gcd(m, n) = 1. This means that (m^{2} − n^{2}) and (m^{2} + n^{2}) must be relatively prime, and so (a, b, c) is a primitive Pythagorean triple.

Since this is true for all m, n satisfying these constraints, and all constraints were necessary, we can find any PPT in this way.

Example 4.1.2: Consider m = 16, n = 15. Then (a, b, c) = (16^{2} − 15^{2}, 2 ∗ 15 ∗ 16, 16^{2} + 15^{2}) = (31, 480, 481).

Alternative Proof of Theorem 4.1.4 (Classical Proof): Now, a^{2} + b^{2} = c^{2}, and a, b have different parity. Take b to be even. Then a and c are both odd. So b^{2} = c^{2}−a^{2} = (c+a)(c−a). Since b is even, b^{2} is a multiple of 4, and (c + a) and (c − a) are each even. So \frac{b^{2}}{4} = \frac{(c+a)}{2} \frac{(c−a)}{2}. Let m^{2} = \frac{(c+a)}{2}, n^{2} = \frac{(c−a)}{2}. Then a = m^{2} − n^{2}, c = m^{2} + n^{2}, and b = 2mn.

9th day, September 28th, notes scribed by Mark Schroeder

Definition: A Pythagorean triangle is a right triangle where all sides have integer lengths. Problem 41 The radius of the inscribed circle of a Pythagorean triangle is always an integer.

Proof: Consider a right-angled triangle with sides a, b, c, and corners A, B, C. We will draw a circle inside the triangle so that it is tangent to all sides a, b, c, and with center g. These tangent points (there are three of them) we will label d, e, f. (Want graphic of the triangle here below but have no idea how to put one there).

Notice: 1.) Af=Radius= Da 2.) Triangle geC is congruent to triangle gfC 3.) Triangle Bgd is congruent to triangle Bge 4.) C = a + b − 2r (r=radius) 5.) 2r = a + b − c 6.) 2|a 7.) 2|b − c

Consider parity: if it is even, we are done. If it is odd, c is odd and either a or b is odd. Thus, r is an integer.

QED

Problem 42: Pythagorean triangles have integer areas. Find a pair of such triangles that have the same area.

Proof: Consider a and b: Either a + b=even, leaving us with an even area or a + b=odd, leaving us also with a even area.

Problem 43: Find all such pairs. some of the pairs written in a table

Length of sides..Area.....Length of sides 1.) 12, 35, 37............210.......20, 21, 29 2.) 28, 195,197..........2730......60, 91, 109 3.) 40, 399, 401.........7980......95, 168, 193 4.) 55, 48, 73............1320......22, 120, 122 5.) 280, 759, 809........106260....385, 552, 673

Problem 44 Prove that congruence modulo n is an equivalence relation. Definition Let a, b be integers. Then a≡b mod n if n|(a − b) Definition An equivalence relation on a set a is a relation that is reflexive, symmetric, and transitive.

Proof: (Reflexive) Let n be some integer greater than zero. Then a−a = 0 = n(0). Therefore n|a − a and thus is a reflexive relation.

(Symmetric) Let k, n, a, b be integers. Notice:

a − b = nk
−1(a − b) = −nk
−a + b = −nk
b − a = −nk

Thus is a symmetric relation.

(Transitive) Let a, b, c, p, n, k be integers. Notice:

a − b = nk
b − c = np
(a − b) + (b − c) = nk + np
a − c = n(k + p)

Thus is a transitive relation.

Since the congruence modulo n is a reflexive, symmetric and transitive, then the relation is an equivalence relation

Problem 45: If a≡b mod n and c ≡ d mod n, then a + c≡b + d mod n and ac≡bd mod n.

Proof: Let k, s, n, a, b, c, d be integers. Notice:

a − b = nk
c − d = ns
(a − d) + (c − d) = nk + ns

a + c − b + d = nk + ns
(a + c) − (b + d) = n(k + s)
c(a − b) = cnk
b(c − d) = bns
ca − cb = cnk
bc − bd = bns
ca − bd = n(ck + bs)
ac − bd = n(ck + bs)

Thus, If a≡b mod n and c ≡ d mod n, then a + c≡b + d mod n and ac≡bd mod n.

Problem 46: If a≡b mod n, then a^{k}≡b^{k} mod n for any positive integer k.

Proof by PMI: em Basis Step:

a′ − b′ = nk
a − b = a≡bmodn

(by assumption) Assume a^{k}≡b^{k} mod n for all positive integers k. em Inductive Step: Consider:

a^{(k+1)}≡b^{(k+1)}modn
a^{(k+1)} − b^{(k+1)} = (a^{k})a − (b^{k})b
ac≡bdmodn
a^{(k+1)}≡b^{(k+1)}modn

Thus we have proved that if a≡b mod n, then a^{k}≡b^{k} mod n for any positive integer. QED

Problem 47: A sort of converse: If a^{k}≡b^{k} mod n for some k > 0, then a≡b mod n.

counterexample 1^{2}≡2^{2} mod 3.

Day 9, September 28, notes scribed by Peter Staats.

Problem 49. Evaluate: 1!+2!+3!+4!+...+100!(mod 12)

1!+2!+3!+4!+...+100!(mod 12) ≡ 9 Solution to problem 49:

4! = 24

so

12 | 4!

and everything thereafter

12 | 4! + 5! + 6! + ... + 100!

therefore:

1! + 2! + 3! + 4! + 5! + ... + 100! ≡ 1! + 2! + 3!(mod 12)
1! + 2! + 3! + 4! + 5! + ... + 100! ≡ 9(mod 12)

Problem 50. Devise and prove a cancellation law for congruence modulo n. That is, is it true ca ≡ cb (mod n) implies that a ≡ b (mod n)?

When does ca ≡ cb (mod n) ⇒ a ≡ b (mod n) we can cancel when n is prime and c is ≢ 0 (mod n)

Assume n is prime we’re given ca ≡ cb (mod n) ca - cb = kn for some k c (a - b) = kn k can be composite so k = k_{1} · k_{2} therefore kn = k_{1} (k_{2} · n)

Case 1. a - b = k_{2}n and c = k_{1}

In case 1 a - b = k_{2}n ⇒ a ≡ b (mod n) Case 2. a - b = 1 and c = nk

But we do not need to worry about case 2 because c≢ 0 (mod n) And here is an interesting little tid-bit. Say n is composite

n = u · v u, v < n

this means that

u · v ≡ 0(mod n)

since

v | n ⇒ 2v ≤ n
u · 2v ≡ 0(mod n)
u · v ≡ u · 2v(mod n)

v ≢ 2v(mod n)

Example: 3 = u, 5 = v

3 · 5 ≡ 0(mod 15)
3 · 10 ≡ 0(mod 15)

but,

5≢ 10(mod 15)

here you can cancel the 5 and still keep congruence with a non-prime module. Notice: One can cancel if c and n are relativlely prime

c(a − b) = kn

a − b = k_{1}n, c · k_{1} = k

It is not important that n is prime, but when c and n are relatively prime. Problem 51 Evaluate: 41^{65} modulo 7.

a ≡ b(mod n)

gives (from problem 46):

a^{k} ≡ b^{k}(mod n)
41 ≡ −1(mod 7)
41^{65} ≡ (−1)^{65} = −1(mod 7)

Therefore

41^{65} ≡ 6(mod 7)

Problem 54 Evaluate: 2^{44} (mod 89)

notice:

89 | 2^{11} − 1
(2^{11})^{4} ≡ 1^{4}(mod 89)
2^{44} ≡ 1(mod 89)

Problem 52: If a is odd, then a^{2} ≡ 1 (mod 8) Prove: If a = 2k + 1 k ≥ 0, then a^{2} = 8b + 1 Proof by Mathematical Induction Basis Step:

n = 0 : a_{0} = 1 1^{2} = (8)0 + 1
n = 1 : a_{1} = 3 3^{2} = (8)1 + 1

Assume: n = k : a_{k} = 2k + 1 where (a_{k})^{2} = 8(b_{n}) + 1 Show: When n = k + 1(a_{k+1})^{2} = 8(b_{k+1}) + 1

a_{k+1} = 2k + 3 = a_{k} + 2
(a_{k} + 2)^{2} = (a_{k})^{2} + 4a_{k} + 4
= 8(b_{k}) + 1 + 4(a_{k} + 1)
8 | 8(b_{k}) + 4(a_{k} + 1)

therefore

(a_{k+1})^{2} = 8(b_{k} + \frac{a_{k} + 1}{2}) + 1

And this is the form in which we need it in. Problem 53: For any a, a^{3} ≡ a (mod 6)

Prove: For any a, a^{3} ≡ a (mod 6) Proof by Mathematical Induction Basis Step:

a = 0 : 0^{3} = 6(b) + 0 b = 0

Assume: It works for all k

a = k k^{3} = 6(b_{k}) + k

Show: k + 1 still holds true

a = k + 1

(k + 1)^{3} = k^{3} + 3k^{2} + 3k + 1 = 6(b_{k}) + k + 3k^{2} + 3k + 1 = 6b_{k} + 3(k^{2} + k) + k + 1

= 6(b_{k} + \frac{k^{2} + k}{2} ) + (k + 1)

Notice: k^{2} + k is even. And this is the form in which we need it in

Problem 55 Find all solutions to 7x ≡ 5 (mod 17)

It is true whenever x = 17n + 8, n ≥ 0 Prove: 17 | 7(17n + 8) − 5 for all n.

7(17n + 8) − 5 = 119n + 56 − 5

= 119n + 51
= 17(3 + 7n)

Therefore, It is divisible by 17

Does it work for any other 17n + a when a ≠ 8 and 0 ≤ a < 17? The possible equivalences mod 17, note that it does only work for 8.

0 ≡ 12 1 ≡ 2 2 ≡ 3 3 ≡ 16 4 ≡ 6 5 ≡ 13 6 ≡ 3 7 ≡ 10 8 ≡ 0 9 ≡ 7 10 ≡ 14 11 ≡ 4 12 ≡ 11 13 ≡ 1 14 ≡ 8 15 ≡ 15 16 ≡ 5

Problem 56 Find all solutions to 9x ≡ 5 (mod 21)

It turns out to be the empty set. Proof by Contradiction

Assume that there is an integer x such that 21 | 9x − 5 Therefore,

\frac{9x − 5}{21}

has to be an integer

\frac{9x}{21} − \frac{5}{21} = \frac{3x}{7} − \frac{\frac{5}{3}}{7} ⇒ 7 | 3x − \frac{5}{3}

This only is true when x is not an integer →← The possible equivalences mod 21, note that it does not ever work, and it only goes in a

cycle.

0 ≡ 14 1 ≡ 2 2 ≡ 11 3 ≡ 20 4 ≡ 8 5 ≡ 17 6 ≡ 5 7 ≡ 14 8 ≡ 2 9 ≡ 11 10 ≡ 20 11 ≡ 8 12 ≡ 17 13 ≡ 5 14 ≡ 14 15 ≡ 2 16 ≡ 11 17 ≡ 20 12 ≡ 8 19 ≡ 17 20 ≡ 5

Problem 57 Find all solutions to 9x ≡ 15 (mod 21)

let,

x = (4 + 7n)
9(4 + 7n) − 15
= 36 − 63n − 15
= 21 + 63n
= 21(1 + 3n)

and this is the correct form. The possible equivalences mod 21, note that it works three times in each cycle, so there is a smaller pattern within the larger modulo.

0 ≡ 3 1 ≡ 12 2 ≡ 0 3 ≡ 9 4 ≡ 18 5 ≡ 6 6 ≡ 15 7 ≡ 3 8 ≡ 12 9 ≡ 0 10 ≡ 9 11 ≡ 18 12 ≡ 6 13 ≡ 15 14 ≡ 3 15 ≡ 12 16 ≡ 0 17 ≡ 9 12 ≡ 18 19 ≡ 6 20 ≡ 15

Moral of 55, 56, 57 In 55 there was one solution in universe mod 17 with an equivalence to 8 In 56 there was no solutions in universe mod 21 with an equivalence to 5 In 57 there were three solutions in universe mod 21 with an equivalence to 15 What is the pattern here and can we generalize it?

Problem 58 State and prove the best theorem(s) you can generalizing the last three results.

The fundamental idea here is to find solutions ax ≡ b (mod n) If gcd(a, n) = 1 then ∃ solutions

Proof

gcd(a, n) = 1 ⇒ ay_{0} + ny_{1} = 1

b(ay_{0} − 1) = b(n(−y_{1}))
aby_{0} − b = n(−y_{1}b)

Assume ax ≡ nb has a solution and gcd (a, n) ≠ 1

Let x_{0} be a solution: Then ax_{0} − b = ny

n = ca + r 0 ≤ r ≤ n

y(ca + r), k > 1, k | (ca + r) ⇒ k | r

Day 10, September 30, notes scribed by Michael Burmaster.

Problem 58 refined and revisited If ax ≡ b (mod n) has solutions, then it has gcd(a, b, n) solutions (mod n).

Proof: Let x_{0} be a solution to ax ≡ b (mod n). Then ax_{0} − b = ny for some y. If k = gcd(a, b, n), we can pull out a k from each term to get a_{1}kx_{0} − b_{1}k = n_{1}ky. Removing the k’s, this leaves

a_{1}x_{0} − b_{1} = n_{1}y with a_{1}, b_{1}, n_{1} relatively prime.

If (x_{0} + j) is a solution for some j, then a_{1}(x_{0} + j) − b_{1} = n_{1}z for some z. This is (a_{1}x_{0} − b_{1}) + a_{1}j = n_{1}z. Substituting in from above, we get

n_{1}y + a_{1}j = n_{1}z.

This implies a_{1}j = n_{1}z − n_{1}y = n_{1}(z − y). Therefore, n_{1} | a_{1}j. Since n_{1} and a_{1} are relatively prime, it must be the case that n_{1} | j.

Thus, solutions of ax ≡ b (mod n) will be of the form x_{0} + n_{1}t, for some t.

This gives the possible solutions {x_{0}, x_{0} + n_{1}, …, x_{0} + n_{1}(k − 1), x_{0} + n_{1}k, x_{0} + n_{1}(k+1), …}. But, x_{0}+n_{1}k is x_{0}+n ≡ x_{0} (mod n), and similarly, x_{0}+n_{1}(k+l) ≡ x_{0} + l (mod n) for all l. Thus, the solutions are

{x_{0}, x_{0} + n_{1}, …, x_{0} + n_{1}(k − 1)},

which gives (k − 1) + 1 = k solutions (mod n).

Therefore, if ax ≡ b (mod n) has solutions, then it has gcd(a, b, n) solutions (mod n).

Problem 48 If a^{k} ≡ b^{k} (mod n) for all k ≥ 2, then a ≡ b (mod n).

We offer a counterexample: Let a = 2, b = 8, and n = 12. We claim that 2^{k} ≡ 8^{k} (mod 12) for all k ≥ 2.

If k = 2, then 2^{k} = 4, which is of the form 12l + 4. Double this, and we get 24l + 8 = 12s + 8 for some s. If we then double this, we get 24s + 16 = 12t + 4 for some t. So:

for k ≥ 2, 2^{k} = \{ \begin{matrix}4 & k is even \\ 8 & k is odd. \end{matrix}

Likewise, if k = 2, then 8^{k} = 64, which is of the form 12d + 4. Multiply this by eight, and we get 96d + 32 = 12r + 8 for some r. Again multiplying by eight, we get 96r + 64 = 12v + 4 for some v. So:

for k ≥ 2, 8^{k} = \{ \begin{matrix}4 & k is even \\ 8 & k is odd. \end{matrix}

Thus, a^{k} ≡ b^{k} (mod n) for all k ≥ 2.

However, it is clear that 2 ≢ 8 (mod 12).

Problem 59 Find a number which leaves remainders 2,3,2 when divided by 3,5,7, respectively.

Many such examples exist: 23, 128, 233, 338, 443, …, 23 + 105k.

Explicitly, we see that:

23 + 105k = 21 + 105k + 2 = 3(7 + 35k) + 2
23 + 105k = 20 + 105k + 3 = 5(4 + 21k) + 3
23 + 105k = 21 + 105k + 2 = 7(3 + 15k) + 2

Problem 60 Find a number which leaves remainders 1,2,3 when divided by 3,5,6, respectively.

No such numbers exist. If such a number x did exist, it would have the property that x = 3n + 1 = 6m + 3. Or, x = 3n + 1 = 3(2m + 1). This means both 3 | x and 3 |̸ x. Contradiction.

Problem 61 When is it possible to solve the system of congruences x ≡ a_{i} (mod n_{i})?

Some thoughts and observations:

First, let us look at some a_{i}, n_{i} combinations for which solutions exist, and some for which they do not:

Some that work... ...and some that don’t.

a_{i}  n_{i}  a_{i}  n_{i}
2, 3, 2  3, 5, 7  1, 2, 3  3, 5, 6
2, 1, 3  4, 25, 21  1, 2, 3  3, 5, 9
2, 3, 2  3, 5, 12  2, 3, 4  3, 5, 12
2, 1, 2  6, 5, 12  2, 2, 6  4, 5, 15
2, 1, 2  6, 5, 4  2, 5, 5  4, 17, 34
2, 5, 4  4, 7, 6  3, 6, 3  5, 7, 28
3, 3, 3  4, 7, 28
5, 5, 5  6, 7, 42
3, 3, 3  5, 7, 42

Drawing on these and other examples, one conjecture has been formulated, but not proven:

Conjecture: The system of congruences x ≡ a_{i} (mod n_{i}) always has solutions if the n_{i} are relatively prime.

But, what if the n_{i} are not relatively prime? Some notes:

1. If the n_{i} have a common factor, so do the a_{i}.

2. If one n_{i} is relatively prime to all the others, it can be disregarded in the search for solutions. It will neither contribute significantly, nor will it limit the possible solutions.

3. We can look at the generating functions of the a_{i}, n_{i} pairs. Let lcm(n_{1}, …, n_{m}) denote the least common multiple of all of the non-relatively prime n_{i}’s in hand. Consider the sets

{a_{i} + kn_{i} (mod lcm(n_{1}, …, n_{m})) | k ∈ Z}.

If the sets from respective pairs intersect, then there is a solution. If not, there are none. Some examples: Consider the pairs 2,4 and 4,6 from the working set a_{i} = 2, 5, 4, n_{i} = 4, 7, 6. We see that lcm(4, 6) = 12. For 2,4, we get the set {2, 6, 10}. For 4,6, we get {4, 10}. Obviously, these intersect at 10. Thus, there is a solution. Now, consider the pairs 6,7 and 3,28 from the non-working set a_{i} = 3, 6, 3, n_{i} = 5, 7, 28. These give lcm(7, 28) = 28. For 6,7, we get the set {6, 13, 20, 27}, and for 3,28, we get {3}. These do not intersect, so there are no solutions.

4. Equivalent to the generating functions is the following:

For any two a_{i}, n_{i} pairs, if a solution exists, it must satisfy the following equation:

a_{i} + xn_{i} = a_{j} + yn_{j}.

In the first case above, we see that 2 + 2 · 4 = 10 = 4 + 1 · 6. Thus, there are solutions. In the second case above, we see that 6 + 7x = 3 + 28y, which means that 3 = 28y − 7x, or 3 = 7(4y − x). So, each side must be divisible by 7, but 7 |̸ 3, so there are no solutions.

5. In the case of two pairs, a_{1}, n_{1} and a_{2}, n_{2}, we have a complete characterization.

Theorem There exists a solution to the system of congruences x ≡ a_{1} (mod n_{1}), x ≡ a_{2} (mod n_{2}) if and only if gcd(n_{1}, n_{2}) divides a_{2} − a_{1}.

Proof: (⇐) Assume that gcd(n_{1}, n_{2}) | (a_{2} − a_{1}). We know that for some s, t, sn_{1} + tn_{2} = gcd(n_{1}, n_{2}).

If a solution exists, then k_{1}n_{1} + a_{1} = k_{2}n_{2} + a_{2}. That is, we want to show that k_{1}n_{1} − k_{2}n_{2} = a_{2} − a_{1}.

Multiplying each side of our original equation by a_{2} − a_{1}, we get:

s(a_{2} − a_{1})n_{1} + t(a_{2} − a_{1})n_{2} = (a_{2} − a_{1})gcd(n_{1}, n_{2}).

Now, dividing by gcd(n_{1}, n_{2}), we get l_{1}n_{1} + l_{2}n_{2} = a_{2} − a_{1}, where

l_{1} = \frac{s(a_{2} − a_{1})}{gcd(n_{1}, n_{2})} and l_{2} = \frac{t(a_{2} − a_{1})}{gcd(n_{1}, n_{2})}.

Because gcd(n_{1}, n_{2}) | (a_{2} − a_{1}), we know that l_{1} and l_{2} are integers. Thus, let k_{1} = l_{1} and k_{2} = −l_{2}, and we see that k_{1}n_{1} − k_{2}n_{2} = a_{2} − a_{1}. So, a solution exists.

(⇒) On the other hand, assume that there exists a solution to x ≡ a_{1} (mod n_{1}), x ≡ a_{2} (mod n_{2}). Then k_{1}n_{1} − k_{2}n_{2} = a_{2} − a_{1}. Obviously, gcd(n_{1}, n_{2}) | (k_{1}n_{1} − k_{2}n_{2}). Therefore, it must also be true that gcd(n_{1}, n_{2}) | (a_{2} − a_{1}).

So, although no complete characterization for Problem 61 has been proven, we have noted several interesting properties of various a_{i}, n_{i} sets, and there are the kernels of a proof sitting here, waiting to be brought into the light.

Day 11, October 2, notes scribed by Millie Kimes.