The great merchant, Hypatia of Alexandria, was dead. In her will, she left her vast fortune not to a person, but to a puzzle. Her wealth was locked in a magnificent chest with not one, but three complex locks.
Her will stipulated: "My fortune shall go to the first of my former
students who can provide the number of coins in this chest. To aid you, I
can say this: the number is more than 100 but less than 200. If you
attempt to count the coins by twos, threes, fours, up to tens, there
will always be a specific number of coins left over."
A young scholar, Euclid, was the first to arrive. He listened to the
executor read the conditions and immediately asked for the remainders.
"The remainders are as follows," the executor said, unrolling a scroll.
Divisible by 2: Remainder 1
Divisible by 3: Remainder 2
Divisible by 4: Remainder 3
Divisible by 5: Remainder 4
Divisible by 6: Remainder 5
Divisible by 7: Remainder 0
Divisible by 8: Remainder 1
Divisible by 9: Remainder 2
Divisible by 10: Remainder 3
Euclid's face fell. "This is chaos! The conditions are not coprime.
Four, six, eight, nine, and ten are all composite! This will take me a
week of calculations!"
Just then, his rival, the quick-witted Sun Tzu, arrived. He glanced at
the list and chuckled. "You are thinking like a laborer, Euclid, not a
mathematician. You are looking at the locks; I am looking at the key."
"And what key is that?" Euclid scoffed.
"The key," said Sun Tzu, "is to see what the number almost is, not what it is. Look at the list. What do you see?"
I will skip the rest of the story. Stories from the past are fine,
but we have a story of the present, and it needs your full attention.
Here it is.
In this note we continue the discussion started in An SO(2,2) Iterated Function System Part 3 - Weyl spinors and null vectors, but now replacing the field of real numbers R by the ring of integers Z. We will show that the following Proposition holds:
Proposition 1. Let A = A = {{a,b},{c,d}} be a non-zero matrix with integer entries, A ∈ Z2⨉2, with det(A) = ad - bc = 0. Then there exist vectors v,w ∈ Z2 such that
A = vwT. (1)
The factorization is unique up to a sign: if A = vwT, then A = (-v)(-wT) is the only other (trivial) variation.
The proof of this Proposition uses the concept of the Greatest Common Divisor (gcd). The standard definition of gcd is:
Definition. For any two integers a,b, at least one of which is nonzero, we denote by gcd(a,b) their greatest common divisor, that is the greatest integer d such that there exist integers e,f such that a = de, b = df. In particular, if (a) is nonzero, we have gcd(0,a) = gcd(a,0) = |a|.
But that definition is tailored for integers, while the concept of gcd is more general, and it has to do with the Unique Factorization Property. So here is a deeper and more formal definition (for non-zero integers)
In other words gcd(a,b) is the product it's the product of all common primes, each raised to the power of the smallest exponent found in either number. The signs of the original integers do not affect the result.
Before proving the Proposition, we first prove the following Lemma
Lemma 1. Let a,b,c,d be integers such that gcd(a,b)=1 and ad = bc. Then there is an integer k such that
c = ka,
d = kb. (1)
Proof. First note that if a = 0 and b = 0, then gcd(a,b) is
undefined, therefore this case is implicitly excluded by the assumption
that gcd(a,b) = 1. Suppose a = 0 and b ≠ 0. Then gcd(0,b) = |b|, and,
since gcd(a,b) = 1, it follows that b = ± 1. From ad = bc it follows
that c = 0. Take k = ±d. Then d = kb and c = ka. Similarly if b = 0 and
a ≠ 0. Let us now assume that both a ≠ 0 and b ≠ 0. By assumption
gcd(a,b) = 1 and ad = bc. Think of the unique prime decomposition of (b)
on the right hand side of ad = bc. None of these primes entering the
composition of b is in (a), since gcd(ab)=1. Therefore they must be all
contained in d. Therefore there is an integer k such that d = kb. But
then, from ad = bc, it follows kab = bc, and, since b ≠ 0, we have c =
ka. QED
We can now return to proving Proposition 1.
Proof (of Proposition 1). Since A is a nonzero
matrix, at least one of it rows is nonzero. Suppose it is the first row:
(a,b). For the second row the proof goes in a complete analogy.
Let g = gcd(a,b). Since at least one of a,b is nonzero, g = gcd(a,b) is well defined. Thus g is a positive integer, and there exist integers a',b' such that
a = ga',
b= gb', (2)
and gcd(a',b') = 1. Since ad = bc, and g is positive, from ad = bc it
follows that a'd = b'c. We can now apply Lemma 1 to deduce that there
exist an integer k such that
c = ka',
d = k b'. (3)
From (2) and (3) it follows that A is of the form:
A = {{ga',gb'},{ka',kb'}}. Setting v = (g,k)T, w = (a',b') we have A = vwT. QED
It follows also from the proof that the decomposition is unique if we require the two components of (w) to be coprime (i.e. if their gcd is 1).
Exercise 1. Find the decomposition of the matrix x^, where x = (3,14,6,13) as mentioned in the Example Part 2.
To be continued...
Afternotes
06-09-25 I switched to Perplexity AI. It seems to be better than ChatGPT and Grok, but still once in a while makes mathematical errors inside proofs. Nevertheless it tries to be careful, writing, for instance: ""However, I should note that this proof requires careful verification of the action of outer automorphisms, and I may have missed some subtle cases."
Here is the beginning of Latex document created by Perplexity as the result of our conversation today:
"The real spin group Spin}(2,2) and its relation to the product Spin(2,2) ≈ SL(2,R)⨉SL(2,R) is a classical but subtle subject with rich automorphism and subgroup structures. While the isomorphism
Spin(2,2) ≈ SL(2,R)⨉SL(2,R)
is well-known, its choices, automorphisms, and related canonical structures require detailed analysis. This document presents the reasoning process, clarifies misconceptions, and synthesizes my understanding based on an extensive conversation. (...)"
Perplexity smartly classifies the isomorphism Spin(2,2) ≈ SL(2,R)⨉SL(2,R) as a "low-dimensional "accident" related to the classification of simple Lie groups and Clifford algebras." Good to know. We are dealing here, in this series, with a VERY special case!
Regarding the intro puzzle, think Euclid was a bit too shy with his assessment that a week of calculations would be needed. :)
ReplyDeleteWe're looking for an odd integer (division by 2 gives remainder 1) between 100 and 200 (initial condition), and division by 5 giving remainder 4 brings down our set of possible solutions to only those numbers ending with digit 9, 10 of them, which can easily be checked one by one. In addition, division by 3 giving remainder 2 means that if we add 1 to our number the resulting number would be multiple of 3 (and of course 2 and 5) while ending with the digit 0. Thus we end up with the set {119, 149, 179} as possible solutions.
However, a number ending with digit 9 evidently won't give remainder 3 when divided by 10, so there's something fishy about the Hypatia's instructions. :)
In other words, following Sun Tzu's hint, if we add 1 to our number, we would end with a number that's multiple of 2, 3, 4, 5 and 6, which are 120 and 180 between 100 and 200, i.e. our number is 119 or 179. Since second one is not multiple of 7, while 119 = 7×17, our number that satisfied the initial and 7 first remainder conditions would then be 119.
Delete119 also satisfies the remainder 2 when divided by 9, but fails to meet mod8 (remainder 7) and mod10 (remainder 9) conditions.
But, as said in previous comment, there seems to be no finite integer numbers that would be odd and giving remainder 4 when divided by 5, meaning they would end in digit 9, while giving remainder 3 when divided by 10 which would mean that they end with digit 3.
You are right. No such finite integer exists. So Hypatia's gold is safe as long as we stay with a finite universe. Infinity and three-valued logic is needed if you are an ambitious treasure hunter.
DeleteEh, would like to think that I am, but being rather thin with infinities, both countable and uncountable, and even thinner with 3-valued logic, would need and ask for a mentor/teacher or at least a hint how to approach the digging site, i.e. the unlocking Hypatia's chest in our case.
DeleteAlthough it's not so much for the gold inside, but more for the challenge, i.e. for learning experience. :)
Question: How wouldn't working with infinity and 3-valued logic 'reconcile' seemingly contradictory conditions of different remainders when divided by 8 and 10 then by 4 and 5?
DeleteAs I see it, since 8 and 10 are multiples of 4 and 5, the remainders of divisions by those numbers should be 'equivalent', i.e. if remainder x of division by 8 for example is less than 4, then x is also remainder of division by 4, while if x is equal or greater than 4, then remainder of division by 4 is x-4.
Since we have 1 and 3 as remainders of divisions by 8 and 10, 1 and 3 would also be remainders of divisions by 4 and 5, while remainders of divisions by 4 and 5 being 3 and 4 means that remainders of divisions by 8 and 10 are 3 or 7 (mod8) and 4 or 9 (mod10).
If we're talking about the same number, how can we square these conditions?
I am not sure. Just an intuition. Intuitions are sometimes right, sometimes wrong. I asked Grok if the concept of the reminder can be defined for transfinite numbers, and Grok told me that it defined for ordinals, though not for cardinals. I didn't ask how three valued logic can be used to find solutions of problems that can't be solved with two-valued logic. Perhaps I will ask it in the future.
DeleteDeepSeek AI "solved" th problem. It's answer is 1799. Which is neither smaller than 200 nor satisfies all of the remainder conditions. So much for this AI. But it also depends on date and time. Perhaps DeepSeek had just a bad day.
DeleteWow. Thanks. Just realized I'm basically tabula rasa about these concepts.
DeleteAs for the DeepSeek, it seems it just likes to show off, with questionable substance to back that up.
Thank you for taking the time to check for the answer. Really appreciate it.
Here i the solution provided by Grok. I din't check the validity of its reasoning though:
DeleteNo such number exists because the system of congruences is inconsistent. For example, the conditions for moduli 2 through 6 imply x≡−1(mod60)x \equiv -1 \pmod{60}x \equiv -1 \pmod{60}
(or equivalently x≡59(mod60)x \equiv 59 \pmod{60}x \equiv 59 \pmod{60}
), but this leads to x≡9(mod10)x \equiv 9 \pmod{10}x \equiv 9 \pmod{10}
, which contradicts the requirement x≡3(mod10)x \equiv 3 \pmod{10}x \equiv 3 \pmod{10}
. Similar contradictions arise with the conditions for moduli 8 and 9.To arrive at this conclusion, rewrite the conditions as congruences:x≡1(mod2),x≡2(mod3),x≡3(mod4),x≡4(mod5),x≡5(mod6),x≡0(mod7),x≡1(mod8),x≡2(mod9),x≡3(mod10).\begin{align*}
x &\equiv 1 \pmod{2}, \\
x &\equiv 2 \pmod{3}, \\
x &\equiv 3 \pmod{4}, \\
x &\equiv 4 \pmod{5}, \\
x &\equiv 5 \pmod{6}, \\
x &\equiv 0 \pmod{7}, \\
x &\equiv 1 \pmod{8}, \\
x &\equiv 2 \pmod{9}, \\
x &\equiv 3 \pmod{10}.
\end{align*}\begin{align*}
x &\equiv 1 \pmod{2}, \\
x &\equiv 2 \pmod{3}, \\
x &\equiv 3 \pmod{4}, \\
x &\equiv 4 \pmod{5}, \\
x &\equiv 5 \pmod{6}, \\
x &\equiv 0 \pmod{7}, \\
x &\equiv 1 \pmod{8}, \\
x &\equiv 2 \pmod{9}, \\
x &\equiv 3 \pmod{10}.
\end{align*}
Observe that the first five are equivalent to x≡−1x \equiv -1x \equiv -1
modulo 2, 3, 4, 5, and 6. The least common multiple of these moduli is 60, so they combine into x≡−1(mod60)x \equiv -1 \pmod{60}x \equiv -1 \pmod{60}
. However, substituting this into the remaining congruences reveals inconsistencies, as shown above (and others, such as x≡3(mod8)x \equiv 3 \pmod{8}x \equiv 3 \pmod{8}
from the combined congruence, but the condition requires x≡1(mod8)x \equiv 1 \pmod{8}x \equiv 1 \pmod{8}
). Thus, no solution exists.
Thanks for grokking the puzzle, although it didn't say anything substantially different from what was written in previous comments, apart from stating that mod9 condition is in contradiction with remainders 1-7 which is basically false as shown above.
Delete100 and 200 are skew binary for 7 and 14 and can be used for three valued logic and I'd like to think it could relate to the puzzle kind of looking like 3 pieces for the remainder list, below 7, at 7, and above 7 but can't really do anything satisfying with it.
DeleteWell, it surely is a smart way to keep readers following the new installments on the blog, leave the in suspension waiting for the end of that story and possible resolution of the puzzle.
DeleteSneaky, but smart. :p
Exercise 1. Find the decomposition of the matrix x^, where x = (3,14,6,13):
ReplyDeletex^ = {{9, 27}, {1, 3}}
v = (9, 1)^T, w = (1, 3)^T
Does this solve the puzzle?
Good!
Delete