A Problem in Pythagorean Arithmetic

A Problem in Pythagorean Arithmetic arXiv:1510.01645v1 [math.LO] 4 Oct 2015 Victor Pambuccian Abstract Problem 2 at the 56th International Mathematical Olympiad (2015) asks for all triples (a, b, c) of positive integers for which ab − c, bc − a, and ca − b are all powers of 2. We show that this problem requires only a primitive form of arithmetic, going back to the Pythagoreans, which is the arithmetic of the even and the odd. 1 Introduction Problem 2 at the 56th International Mathematical Olympiad (2015), proposed by Dušan Djukić, asked contestants to find all triples (a, b, c) of positive integers for which ab − c, bc − a, and ca − b are all powers of 2. Here a “power of 2” is understood to be 2n with n a non-negative integer. As is well known, problems at the IMO should be solvable with elementary means, and our aim is to find out just how elementary a formal theory is needed to solve Problem 2. Since it speaks about positive integers and the operations of addition and multiplication, an axiom system for a theory in which it holds will need to contain the binary operations + and ·, the binary relation <, as well as the constants 0 (so that we can express that all numbers we deal with are non-negative) and 1 (so that we can express the fact that the successor of a number n in the order determined by < is n + 1). 2 The axiom system for PA− and its extensions Thus we need axioms for the usual rules for addition + and multiplication ·, for 1 and 0, that is: A 1 (x + y) + z = x + (y + z) A 2 x+y =y+x A 3 (x · y) · z = x · (y · z) A 4 x·y =y·x A 5 x · (y + z) = x · y + x · z A 6 x+0= x∧x·0= 0 A 7 x·1 =x We also need axioms for inequality <, and a binary operation −, so that we can express the difference between two numbers if the result is positive. These are A 8 (x < y ∧ y < z) → x < z A 10 x < y ∨ x = y ∨ y < x

A 11 x < y → x + z < y + z A 12 (0 < z ∧ x < y) → x · z < y · z A 13 x < y → x + (y − x) = y A 14 0 < 1 ∧ (x > 0 → (x > 1 ∨ x = 1)) A 15 x > 0 ∨ x = 0 A1-A15 represents an axiom system for what is referred to as PA− in [1, pp. 16-18]. Models of PA− consist of numerals, i.e., n = (1 + (1 + . . . + 1)), with 1 ocuurring n times, and, possibly, of nonstandard elements, which are greater than all numerals. By referring to powers of 2, our problem seems to require more, for we do not have the exponential function in our vocabulary. It turns out that we do we need it, for we can express the fact that a is a power of 2 simply by defining the unary predicate P T which stipulates that a positive number a is a power of 2 if and only if all its divisors, except 1, are even: P T (n) :⇔ n > 0 ∧ (∀d) (d|n ∧ d > 1 → 2|d). (1) This definition certainly corresponds to our intuitions regarding powers of 2, but it must not satisfy properties we find to be intrinsic to the notion of “power of 2”, which can be formalized as follows: P T (a) ∧ P T (b) → P T (ab) P T (a) ∧ P T (b) ∧ a < b → a|b P T (a) ∧ a < b ∧ b < 2 · a → ¬P T (b) (2) (3) (4) This is perhaps not so surprising if one thinks that PA− is a very weak theory, in which one cannot even show that among two consecutive numbers one is even and the other none is odd. In fact, for any natural number n, there may be sequences of n consecutive numbers, none !nof which is odd and none of which is even. For the positive cone of Z[X] (here Z[X] is ordered by i=0 ci X i > 0 if and only if cn > 0) is a model of PA− , and the sequence X + 1, . . . , X + n has no even element and no odd element. Yet none of (2)-(4) holds in PA− +A16 " # either, where A16 is the axiom expressed in a language enriched with the unary operation symbol 2· , stating that every number is odd or even: " # " # A 16 x = 2 x2 ∨ x = 2 x2 + 1. To see this, denote by KD [X] !n the ring of polynomials in X with free term in D and with all other coefficients in K, ordered by i=0 ci X i > 0 if and only if cn > 0 (here c0 ∈ D, and ci ∈ K for all 1 ≤ i ≤ n, with cn )= 0), and denote by C(KD [X]) the positive cone of KD [X]. Let Z 12 stand for the ring of dyadic numbers, i.e., all rational numbers of the form 2mn , with m, n ∈ Z and n ≥ 0, and let √ √ R = Z 12 [ 3] stand for the ring whose elements are of the form a + b 3, with a, b ∈ Z 12 . Then C(RZ [X]) % ! $ !n i √ " # n i=1 ai X +a0 = i=1 a2i X i + a20 is a model of PA− + A16. However, given that P T ( 3X), but with 2 √ √ √ ¬P T (3X 2 ), (2) does not hold, and given √ that P T (X), P T ( √3X), X < 3X, yet X ! 3X, (3) does not hold either, and the fact that X < 3X < 2X, with X, 3X, and 2X powers of 2, shows that (4) does not hold. What PA− + A16 lacks is an axiom stating that every fraction can be brought into a form in which numerator and denominator are √not both even. It is an axiom needed for the proof based on considerations of parity of the fact that 2 is irrational. This was, apparently, the oldest form of number theory, as practiced by the Pythagoreans, about which Aristotle tells us in his Metaphysics, 986a, that “Evidently, then, these thinkers also consider that number is the principle both as matter for things and as forming both their modifications and their permanent states, and hold that the elements of number are the even and the odd” (translated by W. D. Ross)

For more on the arithmetic of the even and the odd, see [2]. To state the axiom, we need three more binary operations, "κ, #µ, and ν (so the language in which our Pythagorean Arithmetic is expressed consists of 0, 1, +, ·, <, 2· , κ, µ, ν): A 17 m = κ(m, n) · µ(m, $ n) ∧% n = κ(m, n) · ν(m,$n) ∧(µ(m, n) = 2 µ(m,n) 2 + 1 ∨ ν(m, n) = 2 ν(m,n) 2 % + 1) Notice that A16 becomes superfluous in the presence of A17, as it follows by applying A17 with m = 2, and noticing that, in PA− , if a · b = 2, then a = 1 or b = 1. Pythagorean Arithmetic can thus be axiomatized by {A1-A15, A17}. Throughout the paper, we will use the symbols ≤ and ≥ with their usual meanings. All of (2)-(4) hold in Pythagorean Arithmetic. To see this, notice first that cancelation holds, i.e., satisfies the following a+x=a+y →x=y (5) Proof. Suppose a + x = a + y. By A10, one of x < y, x = y, or y < x must hold. Suppose x = y does not hold. Given the symmetry in x and y of our hypothesis, we may assume, w. l. o. g. that x < y. Then, by A11, we have a + x < a + y as well, thus a + y < a + y, which contradicts A9. ! Cancelation is allowed, i.e., a )= 0 ∧ a · x = a · y → x = y (6) Proof. By (10), we have x < y or x = y, or y < x. If x = y does not hold, then one of x < y or y < x must hold. Suppose x < y. By A12, we have a · x < a · y, contradicting our hypothesis. Same contradiction by assuming y < x. ! Distributivity of multiplication holds over subtraction as well, i.e., b < a → c · a − c · b = c · (a − b) (7) Proof. By A13, b + (a − b) = a, thus, by A5, c · a = c · (b + (a − b)) = c · b + c · (a − b), and, since c · b + (c · a − c · b) = c · a, we must, by (5), c · (a − b) = c · a − c · b. ! Also, odd numbers are never even, i.e., 2 · n + 1 )= 2 · m (8) Proof. Suppose 2 · n + 1 = 2 · m. By A14 and A11 2 · n < 2 · n + 1, thus, 2 · n < 2 · m, so, by A13, 2 · n + (2 · m − 2 · n) = 2 · m. Thus, 2 · n + (2 · m − 2 · n) = 2 · n + 1, and thus, by (5), 2 · m − 2 · n = 1, i.e., by (7), 2 · (m − n) = 1. Since m − n > 0, we have, by A14, m − n > 1 or m − n = 1. Thus, by A7, 2 · (m − n) > 2 or 2 · (m − n) = 2, i.e., 1 > 2 or 1 = 2, none of which can hold, for, by A14 and A11, 0 < 1 and 1 < 1 + 1. ! We also have: 2 · m + 1|a · b ∧ P T (a) → 2 · m + 1|b. (9) Proof. Since 2 · m + 1|a · b, there must be a c such that (2 · m + 1) · c = a · b. By A17 with c instead of m and a instead of n we get that c = κ(c, a)·µ(c, a) and a == κ(c, a)·ν(c, a), with at least one of µ(c, a) and ν(c, a) odd. Plugging in to (2 · m + 1) · c = ab and canceling κ(a, c), we get (2m + 1) · µ(c, a) = ν(c, a) · b. Now ν(c, a) must be odd, for, if it were even, (2 · m + 1) · µ(c, a) would have to be even as well, forcing µ(c, a) to be even (it has to be even or odd, since A16 holds, and, if it were odd, (2m + 1)µ(c, a) would be odd, a contradiction, for a number cannot be both odd and even, by (8)), but one of ν(c, a) and µ(c, a) must be odd. Since ν(a, c) is odd, ν(c, a)|a and P T (a), we must have ν(c, a) = 1, so we have (2 · m + 1) · µ(c, a) = b, so 2 · m + 1|b.

We can now show that (2)-(4) hold in Pythagorean Arithemtic. Suppose P T (a) and P T (b) and let d|ab with d > 1. If d were odd, then, by (9), bearing in mind that P T (a), we would have d|b, but that would contradict the fact that P T (b). This proves (2). Suppose now a < b, P T (a) and P T (b). By A17 we have a = κ(a, b) · µ(a, b) and b = κ(a, b) · ν(a, b). Since a and b cannot have odd divisors greater than 1, and one of µ(a, b) and ν(a, b) has to be odd, the odd one has to be 1 (both cannot be 1, for else a = b). Since we cannot have ν(a, b) = 1, as that would entail b < a or b = a, we must have µ(a, b) = 1, and thus a|b, proving (3). Suppose now a < b, b < 2 · a, and P T (a). By A17, we have a = κ(a, b) · µ(a, b) and b = κ(a, b) · ν(a, b). Given that a can have no odd divisor except for 1, µ(a, b) is either even or 1. If it were 1, then b = a · ν(a, b), and thus 1 < ν(a, b) < 2, contradicting A14, which asks for ν(a, b) − 1 to be 1 or > 1, i.e. ν(a, b) = 2 or ν(a, b) > 2, a contradiction. Thus µ(a, b) is even, so ν(a, b) must be odd. It cannot be 1, for else we would have b ≤ a, so ν(a, b) is an odd number greater than 1. Thus ¬P T (b), proving (4). 3 Problem 2 holds in Pythagorean Arithmetic To turn Problem 2 into a statement that can be proved inside Pythagorean Arithmetic, we need to express it not as a question but rather as a solved problem, one that states what that solutions are and implicitly that there are no other solutions. In this form, its statement is — with S = {(2, 2, 2), (3, 2, 2), &, (11, 6, 2), &, (7, 5, 3), &}, where by (x, y, z), & we have denoted the sequence of all triples obtained by permuting x, y, and z — a · b > c ∧ b · c > a ∧ c · a > b ∧ P T (a · b − c) ∧ P T (b · c − a) ∧ P T (c · a − b) & a=i∧b=j∧c=k → (10) (i,j,k)∈S Theorem The statement (10) can be proved using only the axioms {A1-A15, A17}, i.e., inside Pythagorean Arithmetic. Proof. First, notice that each of a, b, and c has to be greater than 1. That none can be 0 is plain, for if, say a = 0, then a · b > c could not hold, given A15. None of them can be 1 either, for if, say, a = 1, then we would have b > c and c > b, which, after applying A8, would contradict A9. Suppose now that two of a, b, and c were equal, say, a = b. Then we would have P T (a2 − c) and P T (a · (c − 1). The latter implies P T (a) and P T (c − 1), and, since a > 1, P T (a) implies that a is even. If c > 2, then c − 1 > 1, and thus P T (c − 1) would imply that c − 1 is even, i.e., c is odd. But then a2 − c would have to be odd, and since we have P (a2 − c), we would need to have a2 − c = 1, i.e., a2 = c + 1. Since P T (a), we also have, by (2), P T (a2 ), so P T (c + 1) as well. Given that their difference is 2, both c − 1 and c + 1, which have to be even, as c > 2, cannot be multiples of 4. Since both have only even divisors, one of them must be 2. Since c + 1 > 3, we must have c − 1 = 2, so c = 3, and thus, given a2 = c + 1, a = 2. So (2, 2, 3) is the only solution with a = b and c > 2. If c = 2, then P T (a2 − c) and P T (a) imply that 4 ! a, so that a = 2. Thus (2, 2, 2) is the only solution with a = b and c = 2. Given the symmetry in a, b, c of the hypothesis in (10) and the fact that we have already dealt with the case in which two among them are equal, we may assume for the moment that 1 < c < b < a. Let us also denote a · b − c by m, b · c − a by n, and c · a − b by p. Notice that n < p < m. By (3), we must thus have n|p, n|m, and p|m. Notice that m − p = (b − c) · (a + 1) and m + p = (b + c) · (a − 1), so p|(b − c) · (a + 1) and p|(b + c) · (a − 1). (11) One of a + 1 and a − 1 cannot be a multiple of 4, for their difference is 2. If a − 1 is not a multiple of 4, then, since p · x = (b + c) · (a − 1) for some x > 0, and we have either a − 1 = 2 · (2 · k + 1) or a − 1 = 2 · k + 1, we have p · x = (b + c) · 2 · (2 · k + 1) or p · x = (b + c) · (2 · k + 1). In both cases, by (9), 2 · k + 1|x, i.e., x = (2 · k + 1) · y, thus the two options are, after canceling 2 · k + 1 (by (6)), p · y = (b + c) · 2 or p · y = b + c, thus in any case p · y = 2 · (b + c) must hold for some y, and thus p ≤ 2 · (b + c)

If a + 1 is not a multiple of 4, then we arrive analogously to p · y = 2 · (b − c), and thus p ≤ 2 · (b − c). So, in this case as well, (12) holds. Now, b · c + c = (b + 1) · c ≤ a · c = p + b ≤ 2 · (b + c) + b = 3 · b + 2 · c, thus b · c + c < 3 · b + 2 · c, thus, using A11, b · c < 3 · b + c, and, given that 3 · b + c < 4 · b, we get, using A12, c < 4. Thus, we have only two possibilities: (i) c = 2 and (ii) c = 3. Suppose (i) holds. Then we need to have P T (a · b − 2), P T (2 · a − b), and P T (2 · b − a). If a and b were both even, then a · b − 2 would be a multiple of 2, but not of 4, so we would need to have a · b − 2 = 2, which is impossible, since b ≥ 3 and b ≥ 4. One can also easily notice that a and b cannot both be odd, for else a · b − 2 would be odd, and thus would have to be 1, which is impossible for the reasons mentioned above. Thus the pair (a, b) consists of an even and an odd number. Suppose a were odd and b were even, then 2 · b − a would be odd, and thus would have to be 1. Thus a = 2 · b − 1, and thus m = a · b − c = 2 · b2 − b − 2 and p = c · a − b = 3 · b − 2. Since p|m, we have 3 · b − 2|2 · b2 − b − 2. Since 9 · (2 · b2 − b − 2) = (3 · b − 2) · (6 · b + 1) − 16 (13) we must have 3 · b − 2|16. Thus 3 · b − 2 ∈ {1, 2, 4, 8, 16}. However, since b ≥ 3, we have 3 · b − 2 ≥ 7, and thus we can have only 3 · b − 2 = 8, which has no solution b, or 3 · b − 2 = 16, which means b = 6 and a = 2 · b − 1 = 11. So, in case c = 2, we have only (11, 6, 2) as solution. Suppose now (ii) holds. Looking at (11) with c = 3, we notice that not both of b − 3 and b + 3 can be multiples of 4 (given that their difference is 6). If 4 ! b − 3, then b − 3 = i · (2 · k + 1) with i ∈ {1, 2}, and (11) becomes p · x = i · (2 · k + 1) · (a + 1). By (9), x = (2 · k + 1) · y, so we have p · y = i · (a + 1), so p ≤ 2 · (a + 1). Similarly, if 4 ! b + 3, then p · y = i · (a − 1), thus p ≤ 2 · (a − 1). If 4 ! b − 3, then we get p · y = i · (a + 1), thus p ≤ 2 · (a + 1). So, in any case, we have p ≤ 2 · (a + 1), i.e., 3 · a − b ≤ 2 · (a + 1), which means a − b ≤ 2. Since we also have 1 ≤ a − b, we can have only a − b = 1 or a − b = 2. If a = b + 1, then n = 2 · b − 1, which, being odd and a power of 2, must be 1, which is not possible, as it would imply b = 1. If a = b + 2, then m = (b − 1) · (b + 3), and thus we must have P T (b − 1) and P T (b + 3). Since (b + 3) − (b − 1) = 4, one of them must be 4, and, since b ≥ 4, that one cannot be b + 3, so it must be b − 1, so b = 5 and a = 7. ! 4 Pythagrean arithmetic is the right setting We may wonder whether we actually needed all of Pythagorean Arithmetic to prove (10). From a methodological point of view, we have argued that, in the absence of A17, the usual properties of powers of 2 would not hold, and thus the meaning of the terms involved would be altered. In that sense Pythagorean Arithmetic is the right theory in which the question regarding the provability of (10) ought to be raised. From a purely formal point of view, however, one is justified to ask whether (10) does not follow from weaker assumptions. Our proof already shows that it does. All we have used in it is PA− , A16, √ and (9). That this is less than what Pythagorean Arithmetic asks can be seen by noticing that C(Q( 2)Z [X]) is a model of PA− , A16, and (9) (as there are no nonstandard√ powers of 2 in it), but not of Pythagorean Arithmetic (which is plain, as A17 fails for m = X and n = 2 · X). However, the weak theory of the odd and the even, PA− +A16, is not strong enough to prove (10). Theorem PA− +A16 " (10). Proof. If D is an ordered integral domain and R is an ordered integral domain containing D, then we denote by RD [X, Y, Z] the ring ! of polynomials in X, Y, and Z, with free term in D and with all other coefficients in R, ordered by 0≤i,j,k≤n c(i,j,k) X i Y j Z k > 0 (here c(0,0,0) ∈ D, and c(i,j,k) ∈ K for all 1 ≤ i, j, k ≤ n) if and only if c(u,v,w) > 0, where (u, v, w) is the greatest element, in the lexicographic ordering, among all the indexes (i, j, k) of the non-zero coefficients ci,j,k of the terms highest degree, i. e., for which i + j + k is maximal (i.e., (u, v, w) = max{(i, j, k) : c(i,j,k) )= 0; i + j + k = d}, where d is the ! degree of the polynomial 0≤i,j,k≤n c(i,j,k) X i Y j Z k and max is the greatest element in the lexicographic order). Let C(RD [X, Y, Z]) denote the positive cone of RD [X, Y, Z].

0≤i,j,k≤n c(i,j,k) X Y j Zk ( = Then C(RD [X, Y, Z]), with R = Z and D = Z, with 2 " c(0,0,0) # c(i,j,k) i j k − X Y Z + , is a model of PA +A16, but not of (10), for all of XY − Z, 0≤i,j,k≤n,i+j+k$=0 2 2 Y Z − X, ZX − Y are positive and are powers of two. ! 1 2 ! References [1] R. Kaye, Models of Peano Arithmetic. Oxford University Press, Oxford, 1991. [2] V. Pambuccian, The arithmetic of the even and the odd, Rev. Symbolic Logic, submitted. Address: School of Mathematical and Natural Sciences (MC 2352) Arizona State University - West campus P. O. Box 37100 Phoenix, AZ 85306 E-Mail: pamb@asu.edu