3 Number Theory
3.1 Proposals
3.1.1
Proposed by W. J. Blundon. Crux Math. [9: 209].
Prove that every integer \(n > 6\) can be expressed as the sum of two relatively prime integers both of which exceed 1.
Prove that every integer \(n > 11\) can be expressed as the sum of two composite positive integers.
3.1.2
Proposed by W. J. Blundon. Crux Math. [9: 276].
Find all solutions in natural numbers of the system \[ x + y = zw, \quad xy = z + w. \]
Show that the system has infinitely many solutions in integers.
3.1.3
Proposed by W. J. Blundon. Amer. Math. Monthly [72: 665].
Find all solutions in integers of the equation \[ y^2 + y = x^4 + x^3 + x^2 + x. \]
3.1.4
Proposed by W. J. Blundon. Crux Math. [9: 113].
Prove that the Diophantine equation \[ x^n + y^2 = z^{n + 1} \] has infinitely many solutions \((x,y,z)\) for every natural number \(n\).
3.1.5
Proposed by Gali Salvatore. Crux Math. [6: 16].
There is only one integer \(n\) for which the expression \[ E(n) = \frac{12n^3 - 5n^2 -251n + 389}{6n^2 - 37n + 45} \] is an integer. Find this value of \(n\) and show there are no others.
3.1.6
Proposed by Charles W. Trigg. Crux Math. [7:80].
The sum of two positive integers is \(5432\) and their least common multiple is \(223020\). Find the numbers.
3.1.7
Proposed by F. G. B. Maskell, Collège Algonquin. Crux Math. [7: 145].
The number \(2701 = 37 \cdot 73\) is not prime. Show, nevertheless, that \(3^{2701} \equiv 3 \mod 2701\).
3.1.8
Proposed by J. T. Groenman. Crux Math. [9: 113].
Find the remainder when \(72!\) is divided by \(79\).
3.1.9
Proposed by Daniel Roshkar, Susan Wagner H.S. Crux Math. [2: 194].
Show that the only positive integer solution of the equation \(a^b = b^a\), \(a < b\) is \(a = 2\), \(b = 4\).
3.1.10
Proposed by Gordon Raisbeck, Bell Telephone Laboratories, Inc. Amer. Math. Monthly [65: 366].
A. A. Mullin, Amer. Math. Monthly [64: 669] has proved that \[ \phi(n) = \sum_{r=0}^{n} nP_r = \sum_{r=0}^{n} \frac{n!}{(n - r)!} \sim (n!)e \] for large \(n\), where \(\sim\) denotes asymptotic equality. Prove that \[ \phi(n) = [(n!)e], \quad n \geq 1, \] where \([x]\) denotes the largest integer not greater than \(x\).
3.1.11
Proposed by R. C. Thompson, University of California, Santa Barbara. Amer. Math. Monthly [72: 782].
Show that there exists infinitely many sets of three consecutive integers, each of which is a sum of two squares of positive integers.
3.1.12
Proposed by Merrill Barneby, Wisconsin State University. Amer. Math. Monthly [74: 1134].
Show that there exist solutions in positive integers of the system: \[ a + b + c = x + y, \quad a^3 + b^3 + c^3 = x^3 + y^3. \]
In particular, show that there are infinitely, in which \(a\), \(b\), \(c\) form an arithmetic progression.
3.1.13
Proposed by A. M. Kirch, University of Missouri. Amer. Math. Monthly [76: 83].
Find, for each positive integer \(m\) the last three digits of \(m^{100}\).
3.1.14
Proposed by L. F. Meyers, The Ohio State University. Crux. Math. [3: 42].
For which positive integers \(n\) is it true that \[ \sum_{k=1}^{(n - 1)^2} [\sqrt[3]{kn}] = \frac{(n - 1)(3n^2 - 7n + 6)}{4} \quad ? \]
The brackets, as usual, denote the greatest integer function.
3.1.15
Proposed by W. J. Blundon. Canad. Math. Bull. [5: 195].
If \(x \neq 0\) prove that \[ y + y^2 = x + x^2 + x^3 \] has no solution in integers.
3.1.16
Proposed by Charles W. Trigg. Crux Math. [3: 226].
Find triangular numbers of the form \(abcdef\) such that \[ abc = 2def. \]
Editorial Note. A triangular number is any number of the form \(n(n + 1)/2\) where \(n\) is a natural number.
3.1.17
Proposed by Victor Thébault. Amer. Math. Monthly [60: 423].
Determine systems of numeration in which there are one or more four-digit squares of the form \(aabb\) and such that \(a + b\) equals the sum of the digits of the square root.
3.1.18
Proposed by L. J. Mordell, St. John’s College, Cambridge. Amer. Math. Monthly [60: 631].
Prove that there are exactly \((\lambda + 1)^{n + 1} - \lambda^{n + 1}\) sets of \(n\) integers, \(x_1, x_2, ..., x_n\), which satisfy inequalities \[ \lvert x_r \rvert \leq \lambda, \quad \lvert x_r - x_s \rvert \leq \lambda, \quad (r,s = 1, 2,..., n), \] where \(\lambda\) is a positive integer.
3.1.19
Proposed by Erwin Just, Brown Community College. Amer. Math. Monthly [81: 281].
Solve the following Diophantine equations:
\[\begin{align*} x^2(x^2 + y) &= y^{m + 1} \\ x^2(x^2 + y^2) &= y^{m + 1}. \end{align*}\]
3.1.20
Proposed by D. H. Browne. Amer. Math. Monthly [60: 555].
Let \(f(n)\) be the number of ways the integer \(n\) can be decomosed into dissimilar factors [e.g., \(f(1) = 1\), \(f(45) = 3\) because \(1\cdot45 = 3\cdot15 = 5\cdot 9\) but not \(3\cdot3\cdot5\)]. Evaluate \[ \sum_{n=0}^{\infty} \frac{f(2n + 1)}{(2n + 1)^2}. \]
3.1.21
Proposed by D. L. Silverman. Amer. Math. Monthly [70: 759].
Solve \(x^3 = 4y(xy + z^2)\) in nonzero integers \(x\), \(y\), \(z\).
3.1.22
Proposed by Victor Thébault. Amer. Math. Monthly [70: 759].
For each of the following equations \[ x(3x + 1)(6x + 1) = ky^2, \quad k = 1, 2, ..., 6, \] find the solutions in positive integers or prove it insoluble.
3.1.23
Proposed by Leo Moser, University of Alberta. Canad. Math. Bull. [5: 310].
Find all solutions of \(\phi(n) = \tau(n)\). here \(\phi(n)\) is Euler’s totient function and \(\tau(n)\) is the number of divisors of \(n\).
3.1.24
Proposed by W. J. Blundon. Crux Math. [3: 66].
It is well-known that \[ \sqrt{a^2 + 1} = \langle a, \ \overline{2a} \rangle = a + \frac{1}{2a+} + \frac{1}{2a+} + \frac{1}{2a+}... \] for all positive integers \(a\). Solve completely in positive integers each of the equations \[ \sqrt{a^2 + y} = \langle a, \ \overline{x,2a} \rangle \] and \[ \sqrt{a^2 + y} = \langle a, \ \overline{x,x,2a} \rangle, \] where in both cases \(x \neq 2a\).
3.1.25
Proposed by Leo Moser, University of Alberta. Amer. Math. Monthly [64: 365].
What is the smallest positive even integer \(n\) such that in both \(n\) and \(n + 1\) dimensions the regular simplex of edge \(1\) will have a rational number as its content?
3.1.26
Proposed by L. Carlitz, Duke University. Amer. Math. Monthly [64: 437].
Let \(p\) be an odd prime. Show that the number of solutions of the system \[ x + y + z \equiv 3, \quad xyz \equiv 1 \quad \mod p \] is equal to \(p - 2 - (-3/p)\), where \((-3/p)\) denotes the quadratic character of \(-3\). If \(p > 3\), show that the number of solutions is the same for the system \[ x + y + z \equiv 3, \quad x^3 + y^3 + z^3 \equiv 1 \quad \mod p. \]
3.1.27
Proposed by Guy A. R. Guillot. Canad. Math. Bull. [15: 455].
Find the integer solutions of the Diophantine equation \[ y^2 = x(x + y - 1). \]
3.1.28
Proposed by Chandler Davis, Institute for Advanced Study. Amer. Math. Monthly [64: 596].
In how many ways can the first \(n\) positive integers be arranged in alternately increasing and decreasing order? That is, how many permutations \(\pi = \pi(1) \cdot\cdot\cdot \pi(n)\) are there such that the quantities \((-1)^k \left\{\pi(k + 1) - \pi(k)\right\}\), for \(k = 1, ..., n - 1\) have all the same sign?
3.2 Solutions
3.2.1
Solution. Crux Math. [10: 322].
- by Edwin M. Klein, University of Wisconsin-Whitewater.
If \(n = 2k + 1 > 6\), then \(n = 2 + (2k - 1)\), and the two summands both exceed 1 and are relatively prime.
If \(n = 4k > 6\) or \(n = 4k + 2 > 6\), then we have, respectively, \[ n = (2k - 1) + (2k + 1) \text{ or } n = (2k - 1) + (2k + 3). \] In each case, the two summands both exceed 1, and they are relatively prime since they are both odd and differ by a power of 2.
- by F. D. Hammer.
If \(n > 11\), then either \(n - 8\) or \(n - 9\) is composite, and 8 and 9 are.
3.2.2
Solution by Kenneth M. Wilke. Crux Math. [11: 33-34].
- It is clear from the symmetry of the system that it suffices to find all solutions \((x, y, z, w)\) for which \(x \leq y\) and \(x \leq z \leq w\). All other solutions can then be found by permuting \(x\) and \(y\), or \(z\) and \(w\), or \((x,y)\) and \((z,w)\).
The equations can then be combined to give \[ (x-1)(y-1) + (z-1)(w-1) = 2. \]
For \(x = 1\) we obtain only the solution \((1,5,2,3)\); for \(x = 2\), only the solution \((2,2,2,2)\); and no solutions for \(x > 2\).
- There are several infinite sets of integer solutions. One of them is \[ (x,y,z,w) = (0,-k^2,k,-k), k \text{ any integer}. \]
3.2.3
Solution by D. C. B. Marsh, Colorado School of Mines. Amer. Math. Monthly [73: 895].
Multiply the given equation by 4 and add 1 to get \[ 4x^4 + 4x^3 + 4x^2 + 4x + 1 = (2y + 1)^2. \]
For \(x = -1\), \(y = -1\) or \(0\); for \(x = 0\), \(y = -1\) or \(0\); for \(x = 2\), \(y = -6\) or \(5\). (For \(x = 1\), \(y\) is nonintegral.)
For all \(x < -1\) or \(x > 2\), the left-hand side of the above equation is greater than \((2x^2 + x)^2\) but less than \((2x^2 + x + 1)^2\) and cannot be an integral square for integral \(x\), while the right-hand side is an integral square for integral \(y\). Thus, the six solutions listed above are the only integral solutions of the given equation.
3.2.4
Solution by R. B. Killgrove. Crux Math. [10: 232].
For any positive integer \(k\), \[ (x,y,z) = (2k^{n+1},2k^{n+1},2k^n) \] is a solution.
3.2.5
Solution by W. J. Blundon. Crux Math. [7: 31].
We have \[ E(n) = 2n + 9 + \frac{(3n - 4)(5n + 4)}{(3n - 5)(2n - 9)}. \]
Since the consecutive integers \(3n - 4\) and \(3n - 5\) are relatively prime, \(E(n)\) is integral only if \(3n - 5\) divides \(5n + 4\). Hence \(3n - 5\) must also divide \(3(5n + 4) - 5(3n -5) = 37\). Thus \(3n -5 = \pm 1\) or \(\pm 37\). Now \(n\) is not an integer if \(3n -5 = -1\) or \(-37\), and \(E(n)\) is not an integer if \(3n - 5 = 1\) (and \(n = 2\)). The last possibility, \(3n -5 = 37\), yields the unique solution \(n = 14\), since \(E(14) = 41\) is an integer.
3.2.6
Solution by W. J. Blundon. Crux Math. [8: 82].
Suppose the required integers, if they exist, are \(ad\) and \(bd\), where \(a\), \(b\), \(d\) are positive integers and the greatest common divisor \((a,b) = 1\). It easily follows that also \((ab,a+b) = 1\). Since \[ \frac{a+b}{ab} = \frac{ad + bd}{abd} = \frac{5432}{223020} = \frac{28 \cdot 194}{28 \cdot 7965} = \frac{194}{7965}, \] and the first and last fractions are both in lowest terms,we must have \(a + b = 194\) and \(ab = 7965\). Thus \(a\) and \(b\) are the roots of the quadratic \[ x^2 - 194x + 7965 = 0, \] that is, \(\{a,b\} = \{59,135\}\). It follows that \(d = 28\), from which \[ \{ad,bd\} = \{1652,3780\}. \]
Those numbers, which are satisfactory in all respects, constitute the only solution.
3.2.7
Solution by W. J. Blundon. Crux Math. [8: 121-122].
Because \((37,73) = 1\), it is enough to show that \(3^{2701} \equiv 3 \bmod{37}\) and \(3^{2701} \equiv 3 \bmod{73}\). Since \(37\) and \(73\) are primes, Fermat’s Theorem gives \[ 3^{37} \equiv 3 \bmod{37} \quad \text{ and } \quad 3^{73} \equiv 3 \bmod{73}; \] hence \[ 3^{2701} = (3^{37})^{73} \equiv 3^{73} = 3^{37} \cdot 3^{36} \equiv 3 \cdot 1 \equiv 3 \bmod 37 \] and \[ 3^{2701} = (3^{73})^37 \equiv 3^{37} = (3^6)^6 \cdot 3 \equiv 3 \bmod{73}. \]
3.2.8
Solution by W. J. Blundon. Crux Math. [10: 236].
We seek an integer \(r\) such that \(0 \leq r < 79\) and \(72! \equiv r\) (congruences throughout are modulo \(79\)).
From \[ 73 \cdot 74 \cdots \equiv (-6) \cdot (-5) \cdots (-1) = 720 \equiv 9 \] and, above, we obtain (using Wilson’s Theorem [1, p. 116] to get \(78! \equiv -1\)) \[ 9r \equiv 78! \equiv -1 \equiv 315 \] so \(r \equiv 35\), and the required remainder is \(35\).
3.2.9
Solution by W. J. Blundon. Crux Math. [3: 73].
Let \(b = a(1 + t)\), where \(t(>0)\) is rational. The given equation then reduces to \[ a^t = 1 + t < e^t < 3^t, \] so that \(a < 3\). Since \(a = 1\) gives \(t = 0\), we must have \(a = 2\), and it follows easily that \(b = 4\).
3.2.10
Solution by W. J. Blundon. Amer. Math. Monthly [66: 63-64].
We have \[\begin{equation} \begin{split} &(n!)e - \phi(n) \\ &= n! \{1/(n+1)! + 1/(n+2)! + 1/(n+3)! + \dots \} \\ &= 1/(n+1) + 1/(n+1)(n+2) + 1/(n+1)(n+2)(n+3) + \cdots. \end{split} \end{equation}\]
This expression is clearly positive, but is less than \[ (n+1)^{-1} + (n+1)^{-2} + (n+1)^{-3} + \cdots = 1/n \leq 1. \]
Since \(\phi(n)\) is an integer, it follows that \(\phi(n) = [(n!)e]\).
3.2.11
Solution by W. J. Blundon. Amer. Math. Monthly [74: 200].
There is at least one \(n\) (e.g. \(n = 72\)) such that \(n\), \(n + 1\), \(n + 2\) are each sums of two positive squares. From any such set we may obtain another, larger set. In fact, if \(n = a^2 + b^2\), \(n + 1 = c^2 + d^2\), \(n + 2 = e^2 + f^2\), we have \[\begin{align*} n^2 + 2n &= (af - be)^2 + (ae + bf)^2,\\ n^2 + 2n + 1 &= (c^2 - d^2)^2 + (2cd)^2, \\ n^2 + 2n + 2 &= (n + 1)^2 + 1^2. \\ \end{align*}\]
Iteration of this process will produce as many sets as desired.
3.2.12
Solution by W. J. Blundon. Amer. Math. Monthly [76: 84].
If we set \(a = 3d\), \(c = 2b - 3d\), we have \(x + y = 3b\) and the second equation may be reduced to the form \[ (x-y)^2 = (b-8d)^2 - 40d^2, \] one solution of which is \[ x-y = p^2 - 10q^2, \quad b - 8d = p^2 + 10q^2, \quad d = pq. \]
Thus we have the two-parameter family of solutions with \(a\), \(b\), \(c\) in arithmetic progression: \[ a = 3pq, \quad b = p^2 + 8pq + 10q^2, \quad c = 2p^2 + 13pq + 20q^2; \] \[ x = 2p^2 + 12pq + 10q^2, \quad y = p^2 + 12pq + 20q^2. \]
3.2.13
Solution by W. J. Blundon. Amer. Math. Monthly [76: 1071-1072].
Since \((m + 10k)^100 \equiv m^{100} \bmod 1000\), we need only consider the set of least nonnegative residues of \(m\) modulo 10. Applying the Euler Theorem and the Chinese Remainder Theorem, we have
| \(m \bmod 10\) | 0 | 2, 4, 6, 8 | 5 | 1, 3, 7, 9 |
| \(m^{100} \bmod 8\) | 0 | 0 | 1 | 1 |
| \(m^{100} \bmod 125\) | 0 | 1 | 0 | 1 |
| \(m^{100} \bmod 1000\) | 0 | 376 | 625 | 1 |
3.2.14
Solution by W. J. Blundon. Crux Math. [3: 169-171].
Let \(S_n\) be the given sum. If, in accordance with usual practice, we define \(\sum_{k=1}^0 a_k = 0\), then the slated formula holds for \(n = 1,2\), and we can henceforth assume \(n > 2\).
The largest summand in \(S_n\) is \(n - 1\). Let \(N_t\), \(1 \leq t \leq n - 1\), denote the number of times summand \(t\) occurs in \(S_n\), so that \[ S_n = \sum_{t = 1}^{n-1} tN_t. \tag{3.1}\]
Since \[ n - 1 \leq \sqrt[3]{kn} \quad \Longleftrightarrow \quad \frac{(n-1)^3}{n} \leq k \leq n^2, \] we have, in view of the range of \(k\) in \(S_n\), \[ N_{n-1} = (n-1)^2 - \left[\frac{(n-1)^3}{n}\right]. \]
For \(1 \leq t \leq n-2\), since \[ t \leq \sqrt[3]{kn} < t + 1 \quad \Longleftrightarrow \frac{t^3}{n} \leq k < \frac{(t+1)^3}{n}, \] we conclude that \[ N_t = \left[\frac{(t+1)^3}{n}\right] - \left[\frac{t^3}{n}\right] \] if \(n \nmid t^3\) and \(n \nmid (t + 1)^3\); \[ N_t = \left[\frac{(t+1)^3}{n}\right] - \left[\frac{t^3}{n}\right] + 1 \] if \(n \mid t^3\); and \[ \left[\frac{(t+1)^3}{n}\right] - \left[\frac{t^3}{n}\right] - 1 \] if \(n \mid (t+1)^3\). Thus \(S_n\) is increased by \(1\) for each \(t\) such that \(n \mid t^3\).
Let \(\lambda\) be the number of terms in the sequence \(1^3, 2^3, \dotsc, (n-2)^3\) which are divisible by \(n\). Substituting the above results in (Equation 3.1), we have \[ S_n = \lambda + \sum_{t=1}^{n-2} t \left\{ \left[\frac{(t+1)^3}{n}\right] - \left[\frac{t^3}{n}\right]\right\} + (n-1)\left\{(n-1)^2 - \left[\frac{(n-1)^3}{n}\right]\right\} \tag{3.2}\] and \[ S_n = \lambda + (n-1)^3 - \sum_{t=1}^{n-1}\left[\frac{t^3}{n}\right]. \tag{3.3}\]
If \(T_n\) denotes the sum in (Equation 3.2), we can sum \(T_n\) in reverse order and get \[\begin{align*} 2T_n &= \sum_{t=1}^{n-1} \left\{\left[\frac{(n-t)^3}{n}\right] + \left[\frac{t^3}{n}\right]\right\} \\ &= \sum_{t=1}^{n-1} (n^2 - 3nt + 3t^2) + \sum_{t=1}^{n-1} \left\{\left[\frac{t^3}{n}\right] + \left[-\frac{t^3}{n}\right]\right\}. \end{align*}\]
The first of these sums is \[ n^2(n-1) - 3n \cdot \frac{n(n-1)}{2} + 3 \cdot \frac{n(n-1)(2n-1)}{6} = \frac{1}{2} n(n-1)^2; \] and since \[ \left[\frac{t^3}{n}\right] + \left[-\frac{t^3}{n}\right] = \begin{cases} 0 \textrm{ if } n \mid t^3 \\ -1 \textrm{ if } n \nmid t^3 \end{cases}, \] the second sum is \(-(n - 1 - \lambda)\). Thus \[ 4T_n = n(n-1)^2 - 2(n - 1 - \lambda) = (n-2)(n-1)(n+1) + 2\lambda. \]
Now from (Equation 3.2), \[ 4S_n = 4\lambda + 4(n-1)^3 - 4T_n = (n-1)(3n^2 - 7n + 6) + 2\lambda, \] so that \[ S_n = \frac{(n-1)(3n^2 - 7n + 6) + 2\lambda}{4}, \] where \(\lambda\) is the number of terms of the sequence \(1^3, 2^3, \dotsc (n-2)^3\) which are divisible by \(n\). Thus the relation in the proposal holds if and only if \(\lambda = 0\). We will show that \[ \lambda = 0 \ \Longleftrightarrow \ n \textrm{ is squarefree}. \]
If \(n\) is not squarefree, there is a prime \(p\) such that \(p^2 \mid n\); then \(n = p^2a\) and, for \(t = pa\), we have \[ n \mid t^3, \quad 1 \leq t \leq p^2a - 2 = n - 2, \] so \(\lambda \neq 0\).
If \(\lambda \neq 0\) there is an integer \(t\), \(1 \leq t \leq n - 2\), such that \(n \mid t^3\); then \(n\) is not squarefree for otherwise \(n \mid t\) and \(n \leq t\), a contradiction.
3.2.15
Solution by W. J. Blundon. Canada. Math. Bull. [6: 122-123].
Let \(x = ab\) and \(y - x = ac\), where \((b,c) = 1\). Then \(c(ac + 2ab + 1) = a^2b^3\). Now \((b^3,c) = 1\) and \((ac + 2ab + 1,a^2) = 1\). Therefore, \(c = a^2\) and \(b^3 = ac + 2ab + 1 = a^3 + 2x + 1\). Writing the last equation in the form \[ (a-b)^3 + 3(a-b)x + 2x + 1 = 0, \] and putting \(3(a-b) + 2 = z\), we have, on elimination of \(a - b\), \[ 27x = -19/z - 12 + 6z - z^2. \]
Since \(z\) is an integer, there are four possibilities.
\(z = 1\), whence \(27x = -26\), which is impossible.
\(z = 19\), whence \(27x = -260\), which is impossible.
\(z = -19\), whence \(x = -18\). This gives \(ab = -18\), \(a - b = -7\), so that \((a + b)^2 = -23\), which is impossible.
\(z = -1\), whence \(x = 0\), which is contrary to hypothesis.
3.2.16
Solution by W. J. Blundon. Crux Math. [4: 88-89].
If \(def\) represents the number \(m\), then \(abc\) must represent the number \(2m\) and \(abcdef\) represents the number \[ 2001m = T_n = \frac{1}{2}n(n+1), \] where \(T_n\) is the \(n\)th triangular number. Since \(2001 = 3 \cdot 23 \cdot 29\), the congruence \[ n(n+1) \equiv 0 \bmod 2001 \tag{3.4}\] implies \[ n(n+1) \equiv 0 \bmod 3, \quad n(n+1) \equiv 0 \bmod 23, \] and \[ n(n+1) \equiv 0 \bmod 29. \tag{3.5}\]
Since all moduli are primes, each congruence in (Equation 3.5) has exactly two solutions, \(n \equiv 0\) and \(n \equiv -1\), and it follows from an application of the Chinese Remainder Theorem (see Theorem 5.28 in [1,p.118-119], for example) that (Equation 3.4) has exactly \(2 \cdot 2 \cdot 2 = 8\) solutions. These are \[ n \equiv 0,-1,1449,1334,1218,782,666,551 \pmod{2001}. \]
The first three are inadmissible since \(T_{2001}\), \(T_{2000}\) and \(T_{1449}\) all have more than six digits, so the complete solution to our problem is given by the remaining five, as follows: Table.
If the proposer intended the digits of \(abcdef\) to be all distinct, then \(T_{551} = 152076\) is the unique solution.
3.2.17
Partial Solution by W. J. Blundon. Amer. Math. Monthly [61: 646-647].
The assumption is that, if \(x\) is the base of the system of numeration, then integers \(p\), \(q\) exist such that \[ (ax^2+b)(x+1) = (px+q)^2, \] where \(a,b,p,q < x\) and \(a + b = p + q\). Two particular cases give interesting sets of solutions:
Case I: Let \(a + b = p + q = x + 1\).
Elimination of \(b\), \(q\) from the given equation gives \[ (ax-a+1)(x+1)^2 = (px+x-p+1)^2. \tag{3.6}\]
Therefore \(x + 1\) divides \(px + x - p + 1\), so that \(x + 1\) divides \(2p\). Since \(p < x\), it follows that \(x + 1 = 2p\). Substituting in (Equation 3.6) we have \(p = 2a - 1\), \(q = 2a - 1\), \(x = 4a - 3\), \(b = 3a - 2\).
Case II: Let \(a + b = p + q = x - 1\).
Then \[ (ax+a+1)(x+1) = (x-1)(p+1)^2. \tag{3.7}\]
Therefore \(4a + 2 = m(x-1)\), where \(m = 1,2,3,4\) (since \(a \leq x - 1\)). Equation (Equation 3.7) may now be written \[ (4a+2m+1)^2 - m(2p+2)^2 = 1. \]
If \(m\) is \(1\) or \(4\), there is no solutions in integers. If \(m\) is \(2\) or \(3\), we have Pell’s equation. If \(m\) is \(3\), solutions never yield integral values of \(x\), but if \(m\) is 2, the equation becomes \[ (4a+5)^2 - 2(2p+2)^2 = 1 \] the smallest solution of which \(a = 3\), \(p = 5\), successive values being given by the recurrence relations \[ a^\prime = 17a + 12p + 32, \quad p^\prime = 24a + 17p + 46. \]
That the above two cases do not give the complete solution is shown by the examples: \(x = 97\), \(a = 34\), \(b = 94\), \(p = 57\), \(q = 71\); \(x = 161\), \(a = 148\), \(b = 142\), \(p = 154\), \(q = 136\).
Editorial Note. Is it possible to obtain a complete solution to this problem? We do not know the answer!
3.2.18
Solution by W. J. Blundon. Amer. Math. Monthly [62: 48].
If the elements of an ordered set \(x_1, x_2, \dotsc x_n\) are chosen from \(k\) distinct numbers (allowing repetitions), the number of possible distinct sets is \(k^n\). If a specified number (say, the largest) is to be included at least once, the number of distinct sets is \(k^n - (k-1)^n\).
Under the given restrictions on the \(x\)’s, divide the sets into mutually exclusive classes, each class being characterized by the size of its largest \(x_i\). Let \(p\) be a nonnegative integer, and let \(f(y)\)be the number of sets in the class in which the maximum \(x_i\) of every set is \(y\). Then clearly
\[\begin{align*} &f(p) = (\lambda + 1)^n - \lambda^n, &p = 0,1,2, \dotsc, \lambda;\\ &f(-p) = (\lambda - p + 1)^n - (\lambda - p)^n, &p = 1,2,3,\dotsc, \lambda. \end{align*}\]Summing for all the classes, the number of possible sets is \[\begin{align*} (\lambda + 1)\{ (\lambda + 1)^n - \lambda^n\} + &\sum_{p=1}^\lambda \{(\lambda - p + 1)^n - (\lambda - p)^n \} \\ &= (\lambda + 1)^{n+1} - \lambda^{n+1}. \end{align*}\]
3.2.19
Solution by W. J. Blundon. Amer. Math. Monthly [82: 404].
We note first that if \(1 + 4y^n\) is a square, then it is an odd square, say \(1 + 4y^n = (1 + 2v)^2\) with \(v \geq 0\) implying that \(y^n = v(v+1)\). Since \(v\) and \(v + 1\) are relatively prime, both must be \(n\)th powers, implying that either \(v = 0\) or \(n = 1\) so that \(y = v(v+1)\).
Consider equation (1): it is equivalent to \((2x^2 + y)^2 = y^2 + 4y^{m+1}\). If \(m=0\), then the right-hand side is \(y^2 + 4y = (y+2)^2 - 4\) which, by the equation, must be a perfect square. Since two nonzero squares cannot differ by \(4\), necessarily \(x=y=0\) and there is only the trivial solution. Assuming that \(m \geq 1\), the equation can be rewritten as \[ (2x^2 + y)^2 = y^2(1 + 4y^{m-1}), \] implying that \(1 + 4y^{m-1}\) is a square. By the note above, either \(x = y = 0\) or \(m = 2\) and \(y = v(v+1)\). Ignoring the trivial solution we have \(x^2 = v^2(v+1)\) so that \(v\) is of the form \(t^2 - 1\). Thus the nontrivial solutions must be of the form \(m = 2\), \(x = t^3 - 1\) and \(y = t^4 - t^2\), where \(t\) is any integer other than \(0\) or \(\pm 1\). Substitution shows that these are indeed solutions.
Equation (2) reduces to \((2x^2 + y^2)^2 = y^4 + 4y^{m+1}\). Ignoring trivial solutions again, we see that \(m = 0\) is impossible since \(x^2(x^2+y^2) > y\). If \(m = 1\), the right-hand side of the reduced equation is \(y^2(y^2+4)\) and if \(m = 2\), it is \(y^2\{(y+2)^2 - 4\}\). Neither case is possible since two nonzero squares cannot differ by 4. Hence \(m \geq 3\) and the equation becomes \[ (2x^2+y^2)^2 = y^4(1+4y^{m-3}). \]
As in the solution of equation (1), this requires \(m = 4\) and \(y = v(v+1)\). Then \(x^2 = v^3(v+1)^2\) so that \(v\) is of the form \(t^2\). Thus the nontrivial solutions must be of the form \(m = 4\), \(x = t^5 + t^3\), and \(y = t^4 + t^2\), where \(t\) is any nonzero integer. Substitution again verifies that these are solutions.
3.2.20
Solution by W. J. Blundon. Amer. Math. Monthly [61: 722]. For every factorization \(k_1k_2k_3 \dotsm\) of \(2n + 1\) such that \(k_1 < k_2 < \dotsm\), there is associated the term \(a_n\), where \(a_n = (2n+1)^{-2}\). Thus the given expression is equal to
\[\begin{align*} 1 + \sum a_1 &+ \sum a_1a_2 + \sum a_1a_2a_3 + \dotsm \\ &= \prod_{n=1}^\infty (1+a_n) = \prod_{n=1}^\infty [1+(2n+1)^{-2}] \\ &= \frac{1}{2} \prod_{n=0}^\infty [1+(2n+1)^{-2}] = \frac{1}{2} \cosh \frac{1}{2} \end{align*}\]from the well-known infinite product (see [7]).
3.2.21
Solution by W. J. Blundon. Amer. Math. Monthly [71: 560].
Putting \(2xy + x^2 = n\) and eliminating \(y\) we have \(x^4 + z^4 = n^2\), which has no solutions in nonzero integers [15, pp. 100-102].
3.2.22
Editorial Note. In order to follow the solution for this problem, the reader will need to be able to solve the Diophantine equation \(X^4 - 1 = aZ^2\) for the cases \(a = 1\), \(2\), \(3\) and \(15\). This in itself is not an easy question!
When \(a = 1\) or \(2\), it can be shown directly that the equation has no positive integer solutions. The same result holds when \(a = 3\) but is more difficult to prove - the reader could consult [13]. Additional references in that paper show that when \(a = 16\) the unique solution is \(X = 7\), \(Z = 20\), and when \(a = 15\) the unique solution is \(X = 2\), \(Z = 1\).
Solution by W. J. Blundon. Amer. Math. Monthly [63: 195-196]. Since \(x\), \(3x + 1\), \(6x + 1\) are relatively prime in pairs, their square-free factors are given by the following table: Table.
If \(6x + 1 = 5m^2\), or \(3x + 1 = 5m^2\), or \(3x + 1 = 2m^2\), then \(2m^2 \equiv 1 \bmod 3\) which is clearly impossible. Therefore, cases III, VII, VIII, IX all fail, and it follows that \(3x + 1\) and \(6x + 1\) are perfect squares. Let \(6x + 1 = X^2\). Then the original equation becomes \[ X^6 - X^2 = 12ky^2, \quad k = 1, 2, 3, 4, 5, 6. \]
Let \(a\) be the producct of the square-free factors of \(12k\). Then the equation reduces to the form \(X^4 - 1 = aZ^2\), where a is given by Table.
These cases were discussed in the editorial note at the beginning of this solution. The case \(X = 2\) is clearly inadmissible, so the unique solution is given by \(X = 7\), in which case \(x = 8\).
3.2.23
Solution by W. J. Blundon. Canad. Math. Bull. [6: 285-286].
It is required to solve in integers the equation \(Q(n) = 1\), where \(Q(n) = \phi(n)/\tau(n)\). Since \(\phi(n)\) and \(\tau(n)\) are multiplicative, so is \(Q(n)\).
If \(p > q\) (\(p\), \(q\) primes), then \[ Q(p) = \frac{p-1}{2} > \frac{q-1}{2} = Q(q), \] so that, for \(p\) prime, \(Q(p)\) increases strictly with \(p\).
Also, for \(k \geq 1\), \[ \frac{Q(p^{k+1})}{Q(p^k)} = \frac{p(1+k)}{(2+k)} \geq \frac{2(1+k)}{(2+k)} > 1. \]
So, for fixed \(p\), \(Q(p^k)\) increases strictly with \(k\). Clearly \(\min{Q(p^k)} = Q(2) = 1/2\).
Enumerating all \(Q(p^k) \leq 2\), we have \[ Q(2) = 1/2 \quad Q(3) = 1 \quad Q(5) = 2 \] \[ Q(4) = 2/3 \quad Q(9) = 2 \] \[ Q(8) = 1 \] \[ Q(16) = 8/5 \]
Using the fact that \(Q(n)\) is multiplicative, we easily enumerate the complete set of solutions to \(Q(n) = 1\) as follows: \[\begin{align*} 1 &= Q(3) \\ 1 &= Q(8) \\ 1 &= Q(2) \cdot Q(5) = Q(10) \\ 1 &= Q(2) \cdot Q(9) = Q(18) \\ 1 &= Q(3) \cdot Q(8) = Q(24) \\ 1 &= Q(2) \cdot Q(3) \cdot Q(5) = Q(30). \end{align*}\]
Thus all solutions of \(\phi(n) = \tau(n)\) are given by \[ n = 1, 3, 8, 10, 18, 24, 30. \]
3.2.24
Adapted from the solutions of Clayton W. Dodge. University of Maine of Orono, and W. J. Blundon. Crux Math. [3: 228-229].
For the first equation let \[ \sqrt{a^2 + y} = < a, \theta > = a + \frac{1}{\theta} = a + \frac{1}{x + \frac{1}{a + \sqrt{a^2 + y}}} \tag{3.8}\]
where \[ \theta = < \overline{x, 2a} > = < x, 2a, \theta >. \]
Then \[ \theta = x + \frac{1}{2a + \frac{1}{\theta}} = \frac{x(2a\theta + 1) + \theta}{2a\theta + 1}, \] whence \[ \frac{2a}{x} = \frac{2a}{\theta} + \frac{1}{\theta^2} = y. \]
Thus the possible solutions consist of all choices of \(a\), \(x\), \(y\) such that \(2a = xy\) with \(y > 1\). Conversely, it is easily verified that (Equation 3.8) is satisfied whenever \(x = 2a/y\).
Proceeding similarly with the second equation, we have \[ \sqrt{a^2 + y} = < a, \phi > = a + \frac{1}{\phi} = a + \frac{1}{x + \frac{1}{x + \frac{1}{a + \sqrt{a^2 + y}}}} \tag{3.9}\] where \[ \phi = < \overline{x, x, 2a} > = < x, x, 2a, \phi >. \]
Then \[ \phi = x + \frac{1}{x + \frac{1}{2a + \frac{1}{\phi}}} = \frac{(x^2 + 1)(2a\phi + 1) + x\phi}{\phi(2ax + 1) + x}, \] whence \[ \frac{2ax + 1}{x^2 + 1} = \frac{2a}{\phi} + \frac{1}{\phi^2} = y. \]
Since \(2ax + 1\) is odd, \(x^2 + 1\) must also be odd. Thus \(x\) is even and \(y\) is odd, and the condition \(x \neq 2a\) gives \(y > 1\). Let \(x = 2m\) and \(y = 2k + 1\) where \(m\) and \(k\) are positive integers; then \((4m^2+1)(2k+1) = 4am + 1\) and so \[ a = 2mk + m + \frac{k}{2m}. \]
Putting \(k/2m = n\) gives all possible solutions in parametric form: \[ x = 2m, \quad y = 4mn + 1, \quad a = 4m^2n + m + n. \tag{3.10}\]
Finally, substitution in (Equation 3.9) and a great deal of tedious algebra show that (Equation 3.10) does indeed generate all solutions.
3.2.25
Editorial Note. in order to solve this problem, it is necessary to know that the content of the regular simplex of edge \(1\) in \(E_n\) is \(\{(n+1)/2^n\}^{1/2}/n!\). For example, in \(E_2\) the area of the equilateral triangle of side \(1\) is \((\sqrt{3}/2)(1/2!) = \sqrt{3}/4\). In \(E_3\), the volume of the tetrahedron of side \(1\) is \((2/2\sqrt{2})(1/3!) = \sqrt{2}/12\). Here is a vector proof of this formula due to Rudolf Fritsch.
Let \(0 = A_0,A_1,A_2,\dotsc,A_n\) be the vertices of a regular \(n\)-simplex with edge length \(1\). By induction the face opposite \(A_0\) has volume \[ \frac{(n/2^{n-1})^{1/2}}{(n-1)!}. \]
Its center has the vector representation \((A_1 + \dotsc + A_n)/n\). The length of this vector is the height of the simplex and can be easily computed; the scalar products \(A_i \cdot A_j\) for \(i \neq j\) all have the value \(1/2\) since we have unit vectors with an angle of \(60^{\circ}\) between them. So the height is \(\{\sqrt{n(n+1)/2}\}/n\), which gives for the volume of the \(n\)-simplex \[ 1/n^2 \cdot \frac{\left(n/2^{n-1}\right)^{1/2}}{(n-1)!} \cdot \left(\frac{n(n+1)}{2}\right) = \frac{\{(n+1)/2^n\}^{1/2}}{n!} \] as required.
Solution by W. J. Blundon. Amer. Math. Monthly [65: 45-46]. Since \(n\) is to be even, we must have \(n + 1 = x^2\) and \((n+2)/2 = y^2\), where \(x\) and \(y\) are positive integers. This yields the Pellian equation \(x^2 - 2y^2 = -1\), successive solutions of which are \((1,1), (7,5), (41,29), (239,169), \dotsc\). Since \(x > 1\), \(\min{x} = 7\), so that \(\min{n} = 48\). The next smallest values of \(n\) are clearly \(41^2 - 1 = 1680\) and \(239^2 - 1 = 57120\).
3.2.26
Solution by W. J. Blundon. Amer. Math. Monthly [65: 373-374].
We have \[ (x-y)^2 = (x+y)^2 - 4xy \equiv (3-z)^2 - 4/z \equiv (z-1)^2(z-4)/z \bmod{p}. \]
If \(x \equiv y \bmod{p}\), then \(z \equiv 1\) or \(4\). This leads to exactly two solutions, namely \((1,1,1)\) and \(((p-1)/2, (p-1)/2, 4)\).
If \(x \not\equiv y \bmod{p}\), then \((z-4)/z\) is a quadratic residue modulo \(p\). Let \((z-4)/z \equiv n^2\), where \(n^2 \not\equiv 0,1,-3 \bmod{p}\). Thus \(z\) assumes \(\frac{1}{2}(p-1) - 2\) or \(\frac{1}{2}(p-1) - 1\) distinct values according as \(-3\) is or is not a quadratic residue modulo \(p\). It follows that the number of solutions with \(x \not\equiv y\) is double this number, namely \(p - 4 - (-3/p)\). The total number of solutions of this system is thus \(p - 2 - (-3/p)\).
If we apply the transformation \(2x = Y + Z\), \(2y = Z + X\), \(2z = X + Y\), to the system (1) we obtain \[\begin{align*} X + Y + Z &\equiv x + y + z \equiv 3 \bmod{p}, \\ X^3 + Y^3 + Z^3 &\equiv (X + Y + Z)^3 - 3(Y + Z)(Z + X)(X + Y) \\ &\equiv (x+y+z)^3 - 24xyz \equiv 3 \bmod{p}. \end{align*}\]
Since the transformation is linear with nonzero determinant, the number of solutions is the same for both systems. The condition \(p > 3\) excludes the the exceptional case \((X,Y,Z) \equiv (0,0,0)\) which is a solution of the second system and yet is the transform of \((x,y,z) \equiv (0,0,0)\) which is not a soolution of the first.
It is interesting to note that, upon replacing congruence modulo \(p\), by equality in the above, we may use the substitution \((z-4)/z = m^2 / n^2\) to obtain an infinity of rational solutions for the Diophantine equation \[ X^3 + Y^3 + Z^3 = 3, \] and hence an infinity of itegral solutions of \[ a^3 + b^3 + c^3 = 3d^3, \] namely \[\begin{align*} &a = 4n^3 - 3mn^2 - m^3, &b = 4n^3 + 3mn^2 + m^3, \\ &c = -5n^2 - 3m^2n, &d = n^3 - m^2n. \end{align*}\]
3.2.27
Solution by W. J. Blundon. Canada. Math. Bull. [17: 311].
Let \(x = ca\) and \(y = cb\) where \((a,b) = 1\) and where, without loss of generality, we may take \(b \geq 0\). Then \(cb^2 = a(ca + cb - 1)\). Now, \((c, ca + cb - 1) = 1\) and \((b^2, a) = 1\). Therefore we have either \(c = a\), \(b^2 = ca + cb - 1\), \(a^2 + ab - b^2 = 1\); or \(c = -a\), \(b^2 = -(ca + cb - 1)\), \(a^2 + ab - b^2 = -1\).
Put \(2a + b = \pm d\) where \(d \geq 0\), and we then obtain the Pell equation \(d^2 - 5b^2 = \pm 4\). It is well known that the nonnegative solutions of this equation are given by \(b = F_n\), \(d = F_n + 2F_{n-1}\), where \(F_n\) is the \(n\)th Fibonacci number [17, pp. 29-30]. Since \(n\) is even or odd according as \(c = +a\) or \(-a\), we may put \(c = (-1)^na\). Now \(2a + b = \pm d\) gives \(a = F_{n-1}\) or \(-F_{n+1}\). Thus the general solution is \(y = (-1)^nF_nF_{n-1}\), \(x = (-1)^n(F_{n-1})^2\) or \((-1)^{n+1}F_n^2\). Solutions for small \(n\) are given by: Table.
3.2.28
Solution by W. J. Blundon. Amer. Math. Monthly [65: 533-534].
Let \(P_n\) be the required number of arrangements of the first \(n\) positive integers, under the restriction that the common sign of the stated quantities is negative. The integer \(n\), being the largest in the set, is necessarily of the form \(\pi(2i)\), \(i = 1,2, \dotsc, [n/2]\). The integers to the left of \(n\) can be chosen in \[ \binom{n - 1}{2i - 1} \] ways, and each such selection can be arranged in \(P_{2i-1}\) ways. The integers to teh right of \(n\) can be arranged in \(P_{n-2i}\) ways. Hence \[ P_n = \sum_{i=1}^{[n/2]} \binom{n - 1}{2i - 1} P_{2i - 1}P_{n - 2i}, \quad n = 1,2, \dotsc, \] where, for convenience, we define \(P_0 = 1\). Putting \(P_n = n!Q_n\), we have \[ Q_0 = 1; \quad nQ_n = \sum_{i=1}^{[n/2]} Q_{2i-1}Q_{n-2i}, \quad n = 1,2, \dotsc. \]
Define \(f(x) = \sum_{n=0}^\infty Q_nx^n\). Then it is easily verified that \[ \{f(x)\}^2 = -1 + 2f^\prime(x). \]
The solution of this differential equation gives \[ \sec x + \tan x = f(x) = \sum_{n=0}^\infty p_nx^2/n!. \]
From the well-known expansions of \(\sec x\) and \(\tan x\), we have
\[ \begin{cases} B_n \quad n \textrm{ even,} \\ \frac{2^{n+1}(2^{n+1}-1)}{n+1}B_n \quad n \textrm{ odd,} \end{cases} \]
where the \(B_i\)’s are alternately Bernoulli numbers and Euler numbers \((1/6, 1, 1/30, 5, \dotsc)\).
We now remove the restriction of the first sentence of this solution. Then, by symmetry, the required number of arrangements is \(2P_n\), (except when \(n = 1\), when the restriction has no meaning). The number of arrangements for small \(n\) is given by Table.