Finding triplets $(a,b,c)$ such that $\sqrt{abc}\in\mathbb N$ divides $(a-1)(b-1)(c-1)$
When I was playing with numbers, I found that there are many triplets of three positive integers $(a,b,c)$ such that
- $\color{red}{2\le} a\le b\le c$
- $\sqrt{abc}\in\mathbb N$
- $\sqrt{abc}$ divides $(a-1)(b-1)(c-1)$
Examples : The followings are positive integers. $$\frac{(2-1)(8-1)(49-1)}{\sqrt{2\cdot 8\cdot 49}},\ \frac{(6-1)(24-1)(529-1)}{\sqrt{6\cdot 24\cdot 529}},\frac{(7-1)(63-1)(3844-1)}{\sqrt{7\cdot 63\cdot 3844}}$$
Then, I began to try to find every such triplet. Then, I found $$(a,b,c)=(k,km^2,(km^2-1)^2)$$ where $k,m$ are positive integers such that $k\ge 2$ and $km^2\ge 3$, so I knew that there are infinitely many such triplets. However, I can neither find the other triplets nor prove that there are no other triplets. So, here is my question.
Question : How can we find every such triplet $(a,b,c)$?
Added : There are other triplets : $(a,b,c)=(k,k,(k-1)^4)\ (k\ge 3)$ by a user user84413, $(6,24,25),(15,15,16)$ by a user Théophile. Also, from the first example by Théophile, I got $(2k,8k,(2k-1)^2)\ (k\ge 3)$.
Added : $(a,b,c)=(k^2,(k+1)^2,(k+2)^2)\ (k\ge 2)$ found by a user coffeemath. From this example, I got $(k^2,(k+1)^2,(k-1)^2(k+2)^2)\ (k\ge 2)$.
Added : I got $(a,b,c)=(2(2k-1),32(2k-1),(4k-3)^2)\ (k\ge 5)$.
Added : I got $(a,b,c)=(k,(k-1)^2,k(k-2)^2)\ (k\ge 4)$.
Added : A squarefree triplet $(6,10,15)$ and $(4,k^2,(k+1)^2)\ (k\ge 2)$ found by a user martin.
Added : user52733 shows that $(6,10,15)$ is the only squarefree solution.
Solution 1:
Too long for a comment:
In addition to the rather lengthy
\begin{align} &(m^2,\\ &((-1)^{2 k} \left(2 (-1)^k k m+(-1)^{k+1} (m+2)+m-6\right)^2)/16,\\ &\left((-1)^k \left(2 (-1)^k k m+(-1)^{k+1} (m+2)+m-6\right)+1\right)^2/4)\\ \end{align}
we also have $(a,b,c):$
\begin{align} &\left(k^3+k^2+k+1,k^3+k^2+k+1,k^4\right)\\ &\left(k^4+k^2+1,k^4+k^2+1,k^6\right)\\ &\left(k m^2,k m^2 \left(k m^2-2\right)^2,\left(k m^2 \left(k m^2-3\right)+1\right)^2\right)\\ \end{align}
and for $f(n)=(n-1)^2$ we also have
\begin{align} &\left(k^2,f^{2 n-1} \left((k m+1)^2\right),f^{2 n} \left((k m+1)^2\right)\right)\\ \end{align}
where $f^n$ is $f$ iterated $n$ times for $n \geq 1.$
However, even for fixed $a,$ the above formulae don't catch all of the solutions (and they say nothing of non-square $a$ combinations), and yet for each $a$ there seem to be multiple (infinite?) solutions.
Examples: case $a=8:$
A straightforward brute-force search for $(8,b,c);\ (b,c)<1000$ gives triples
$(8,2,49),(8,8,49),(8,18,49),(8,18,289),(8,32,49),(8,32,961),(8,49,72),(8,49,288),(8,289,392),(8,392,529),$
where it is immediately apparent that the same numbers recur a number of times. Removing the $8$ and graphing shows the connectedness more clearly:
Searching for $c$ only, using the distinct elements from the initial search (eg $(8,49,c)$, etc.) up to $10^5$ reveals further connections:
$(8,49,c)$ for example turns up $6$ triplets: $(8,49,2),(8,49,8),(8,49,18),(8,49,32),(8,49,72),(8,49,288)$
It may be more pertinent to ask then, are there infinitely many triplets for fixed $a?$ Certainly where $a$ is square, this is the case, but it is less clear whether this is the case when it is not.
It may also be worthwhile pursuing the idea of primitive pairs $(a,b).$
Solution 2:
Still in extended comment territory, but I wanted to confirm @martin's conjecture that $(6, 10, 15)$ is the only squarefree solution.
Notations:
- $\mathbb{N} = \lbrace 1, 2, 3, \dotsc \rbrace$.
- The statement "$d$ divides $n$" is abbreviated $d \mid n$ when approriate.
The first statement is a quick rewrite.
Lemma 1: Suppose $a, b, c \in \mathbb{N} \setminus \lbrace{1\rbrace}$ satisfy
\begin{equation} \tag{*} \sqrt{abc} \in \mathbb{N}. \end{equation}
Then the following are equivalent.
\begin{align}
\sqrt{abc} & \mid (a-1)(b-1)(c-1) \tag{1a}\\
\sqrt{abc} & \mid ab + bc + ca - (a + b + c) + 1 \tag{1b}
\end{align}
Proof. Suppose that $a, b, c \in \mathbb{N} \setminus \lbrace{1\rbrace}$ satisfies (*). Multiplying out, $$(a-1)(b-1)(c-1) = abc - (ab + bc + ca) + (a + b + c) - 1,$$ and certainly, whenever $\sqrt{abc} \in \mathbb{N}$, $\sqrt{abc}$ divides $abc$. Thus, if (1a) holds, then $\sqrt{abc}$ divides both $abc$ and $(a-1)(b-1)(c-1)$, and hence divides $$abc - (a-1)(b-1)(c-1) = (ab + bc + ca) - (a + b + c) + 1.$$ So (1b) holds. The reverse direction is similar. $\square$
We now note some divisibility conditions. We start with an observation.
Lemma 2: Let $a, b, c \in \mathbb{N} \setminus \lbrace{1\rbrace}$ satisfy (*), and let $p$ be a prime divisor of $abc$. Then either $p$ divides at least two of $a$, $b$, and $c$, or $p^2$ divides one of $a, b, c$.
The proof is an undergraduate number theory exercise, following from, e.g., Lemmas 2.1 and 2.4 of Jones and Jones, Elementary Number Theory.
The natural question is, "Can $p$ divide all three of $a$, $b$, and $c$?" The answer is no, and the argument holds for all divisors $d$ to an extent.
Lemma 3: Suppose $a, b, c \in \mathbb{N} \setminus \lbrace{1\rbrace}$ satisfy (*) and (1b). Fix $d \in \mathbb{N}$.
- If $d$ divides $a$ and $d$ divides $b$, then $d$ divides $c - 1$.
- If $d^2$ divides $a$, then $d$ divides $(b-1)(c-1)$.
Proof, part 1. Suppose $a, b, c \in \mathbb{N} \setminus \lbrace{1\rbrace}$ satisfy (*) and (1b), and also suppose that for some $d \in \mathbb{N}$, $d$ divides both $a$ and $b$. Then certainly $d^2$ divides $abc$, so $d$ divides $\sqrt{abc}$. Since (1b) holds and divisibility is transitive, $d$ divides $(ab + bc + ac) - (a + b + c) + 1$. Since $d$ divides $a$ and $b$, it clearly divides $ab$ and $bc$ and $ac$. Hence, $d$ divides $$N := ab + bc + ac - (a + b).$$
Yet we already said that $d$ divides $$(ab + bc + ac) - (a + b + c) + 1 = N - c + 1.$$
Thus, $d$ divides $$N - (N - c + 1) = c - 1. \quad \square.$$
Proof, part 2 (Modular Arithmetic). Suppose $a, b, c \in \mathbb{N} \setminus \lbrace{1\rbrace}$ satisfy (*) and (1b). By Lemma 1, (1a) holds. Suppose that for some $d \in \mathbb{N}$, $d^2$ divides $a$. If $d = 1$, then by $b, c \in \mathbb{N} \setminus \lbrace{1\rbrace}$, $d$ divides $(b-1)(c-1)$, so assume $d \neq 1$. Since $d^2 \mid a$, $d^2 \mid abc$ and $d \mid \sqrt{abc}$. By (1a) and transitivity of division, $d$ divides $(a-1)(b-1)(c-1)$, or equivalently, $$(a-1)(b-1)(c-1) \equiv 0 \pmod{d}.$$ Yet $d^2$, and hence $d$, divides $a$, so $(a-1) \equiv -1 \pmod{d}$. Yet by $d \geq 2$, $-1$ is certainly a unit in $\mathbb{Z}/d\mathbb{Z}$, since $(-1)^2 = 1$. Hence, [the equivalence class of] $(a-1)$ is a unit in $\mathbb{Z}/d\mathbb{Z}$, hence not a zero-divisor. Thus, the only way for $(a-1)(b-1)(c-1) \equiv 0 \pmod{d}$ is if $(b-1)(c-1) \equiv 0 \pmod{d}$, i.e., $d$ divides $(b-1)(c-1)$. $\square$
Lemma 3, part 1 (hereafter, Lemma 3.1) shows in particular that $\gcd(a, b)$ divides $(c-1)$ for any solution $(a, b, c)$ (and the corresponding statements by permuting the letters). Lemma 3, part 2 is weaker, but is slightly stronger if $d$ is a prime:
Corollary 4: Suppose $a, b, c \in \mathbb{N} \setminus \lbrace{1\rbrace}$ satisfy (*) and (1b), and suppose that $p$ is some prime divisor of $abc$. Then at least one of $a$, $b$, and $c$ is congruent to $0 \pmod{p}$, and at least one of $a$, $b$ and $c$ is congruent to $1 \pmod{p}$.
Proof. Suppose $a, b, c \in \mathbb{N} \setminus \lbrace{1\rbrace}$ satisfy (*) and (1b), and suppose that $p$ is some prime divisor of $abc$. By Lemma 2, either $p$ divides 2 of $a$, $b$, and $c$, or $p^2$ divides one of $a$, $b$, and $c$. In the former case, without loss of generality $p$ divides $a$ and $b$, and applying the $d = p$ case of Lemma 3.1, $p$ divides $c-1$, i.e., $c \equiv 1 \pmod{p}$. In the latter case, without loss of generality, $p^2$ divides $a$, and applying the $d = p$ case of Lemma 3.2, $p$ divides $(b-1)(c-1)$. Since $p$ is prime, $p \mid (b-1)$ or $p \mid (c-1)$, i.e., $b \equiv 1 \pmod{p}$ or $c \equiv 1 \pmod{p}$. $\square$
For the next divisibility condition, we note that the easiest way to satisfy (*) [apart from $a$, $b$, $c$ each being square] is for $c = ab$. We show that such a combination never gives a solution to (1b). We need the following rule, using the order properties of $\mathbb{N}$.
Lemma 5: If $m, n \in \mathbb{N}$ and $m$ divides $n$, then $m \leq n$.
The proof is a standard undergraduate number theory fact (e.g., Jones and Jones, Elementary Number Theory, Exercise 1.3(d)).
Lemma 6: Let $a, b \in \mathbb{N} \setminus \lbrace{1\rbrace}$, and let $c := ab$. Then $a, b, c$ do not satisfy (1b).
Proof. Let $a, b \in \mathbb{N} \setminus \lbrace{1\rbrace}$, and let $c := ab$. Then (*) holds, with $\sqrt{abc} = \sqrt{a^2 b^2} = ab$ (by $a, b > 0$). Suppose, by way of contradiction, that $a, b, c$ do satisfy (1b). Then $ab$ divides \begin{align} ab + ac + bc - (a + b + c) + 1 &= ab + a^2 b + ab^2 - (a + b + ab) + 1\\ & = ab(1 + a + b - 1) - (a + b) + 1\\ & = ab(a + b) - (a + b) + 1 \end{align}
Yet $ab$ clearly divides $ab(a + b)$. Thus, $ab$ divides $$ab(a + b) - [ab(a + b) - (a + b) + 1] = a + b - 1.$$
In particular, $a \mid a + b -1$, and $a \mid a$, so $a \mid b - 1$; similarly, $b \mid a - 1$. Since $a$, $a-1$, $b$, and $b-1$ are positive integers, by Lemma 5, $a \leq b - 1$ and $b \leq a - 1$, so $a \leq a - 2$, a contradiction. $\square$
Sadly, although our divisibility checks reduce our workload, they are not yet a characterization; as shown by a computer search, the cases $(3, 4, 27)$, $(7, 8, 14)$, and $(6, 15, 40)$ [among others] allow $\sqrt{abc} \in \mathbb{N}$ and satisfy all the divisibility checks above, but do not satisfy (1a).
Now we get to the main proof. Our first argument is that the square freeness, combined with Lemmas 2 and 6, force a large amount of common factors.
Proposition 7: Let $a, b, c \in \mathbb{N} \setminus \lbrace{1\rbrace}$ satisfy (*) and (1b). If in addition, $a$, $b$, $c$ are squarefree, then we may write \begin{align} a &= PQ\\ b & = PR\\ c & = QR \end{align} where $P, Q, R \in \mathbb{N} \setminus \lbrace{1\rbrace}$ are pairwise coprime.
Proof. Since $a$ is squarefree, for any prime $p$, $p^2 \nmid a$. Thus, $a$ is a product of distinct prime factors. Yet by Lemma 2, for any prime $p$ dividing $a$, $p$ must therefore divide one of $b$ or $c$; by Lemma 3.1, it divides exactly one of $b$ or $c$. Thus, we may write $a = PQ$ where $$P = \prod_{\substack{ p \text{ prime}\\ p \mid a \text{ and } p \mid b }} p; \quad Q = \prod_{\substack{ p \text{ prime}\\ p \mid a \text{ and } p \mid c }} p,$$ where the empty product is $1$. Similarly, since $b$ and $c$ are also squarefree, then we may write $b = PR$ and $c = QR$, where $$ R = \prod_{\substack{ p \text{ prime}\\ p \mid b \text{ and } p \mid c }} p.$$ Obviously, $P$, $Q$, and $R$, being factors of squarefree numbers, are squarefree. Also, $P$ and $Q$ are coprime, else $a$ would not be squarefree; similarly $P$ and $R$ are coprime, and $Q$ and $R$ are coprime.
Moreover, $P \neq 1$; else, $a = Q$, $b = R$, and $c = QR = ab$, which by Lemma 6 cannot hold. Similarly, $Q \neq 1$ and $R \neq 1$. $\square$
Now, it suffices to show that by the power of Lemma 3.1, any solution with the above decomposition cannot hold.
Proposition 8: Fix $P, Q, R \in \mathbb{N} \setminus \lbrace{1\rbrace}$, and define \begin{align} a &:= PQ\\ b &:= PR\\ c & := QR \end{align} Then (*) holds. If in addition, $P$, $Q$ and $R$ are pairwise coprime, and $a, b, c$ satisfy (1b), then up to permutations, $P = 2$, $Q = 3$, and $R = 5$; i.e., $(a, b, c)$ is $(6, 10, 15)$ up to permutations.
Proof. Fix $P, Q, R \in \mathbb{N} \setminus \lbrace{1\rbrace}$, and define $a$, $b$, $c$ as above. Then clearly $abc = (PQR)^2$, so $\sqrt{abc} = PQR$ is in $\mathbb{N}$. (*) holds.
Suppose in addition that $P$, $Q$ and $R$ are pairwise coprime, and that (1b) holds; i.e., $PQR$ divides \begin{align} ab + ac + bc - (a + b + c) + 1 & = P^2QR + PQ^2R + PQR^2 - (PQ + PR + QR) + 1\\ & = PQR(P + Q + R) - (PQ + PR + QR) + 1 \end{align} Yet clearly, $PQR$ divides $PQR(P + Q + R)$. Hence, $PQR$ divides $$PQR(P + Q + R) - \left[ PQR(P + Q + R) - (PQ + PR + QR) + 1 \right] = PQ + PR + QR - 1.$$
Since $P, Q, R \in \mathbb{N} \setminus \lbrace{1\rbrace}$, $PQ + PR + QR - 1 \geq 2$, so we may apply Lemma 5 and get that \begin{equation} 0 < PQR \leq PQ + PR + QR - 1 \tag{2} \end{equation}
Claim 1. At least one of $P$, $Q$, and $R$ is less than $3$.
Suppose, by way of contradiction, that $P \geq 3$, $Q \geq 3$, and $R \geq 3$. Then \begin{align} PQ + PR + QR - 1 & = \frac{PQR}{R} + \frac{PQR}{Q} + \frac{PQR}{P} - 1\\ & \leq \frac{PQR}{3} + \frac{PQR}{3} + \frac{PQR}{3} - 1\\ & = PQR - 1 < PQR \end{align} Yet this contradicts (2).
Since $P, Q, R$ are each at least $2$, at least one of them, say $P$, is equal to $2$. Since $Q$ and $R$ are coprime to $P$, they must be at least $3$.
Claim 2. One of $Q$ and $R$ is equal to $3$.
Suppose by way of contradiction that $Q > 3$ and $R > 3$. Then by $Q$ coprime to $P$, $Q \neq 4$, so $Q \geq 5$; similarly, $R \geq 5$. Thus, \begin{align} PQ + PR + QR - 1 & = \frac{PQR}{R} + \frac{PQR}{Q} + \frac{PQR}{P} - 1\\ & \leq \frac{PQR}{5} + \frac{PQR}{5} + \frac{PQR}{2} - 1\\ & = \frac{9}{10} \, PQR - 1 < PQR \end{align} Again, we contradict (2).
Thus, without loss of generality, $Q = 3$. Now the second inequality in (2) reads \begin{align} 6R &\leq 6 + 2R + 3R -1, &&\text{or}\\ 6R & \leq 5R + 5, &&\text{or}\\ R & \leq 5 \end{align} Since $R > 1$, and $R$ is coprime to $2$ and $3$, then $R = 5$. $\square$
Combining Propositions 7 and 8, we have our result.
Solution 3:
(Too long for a comment.)
The two solutions,
$$a,\,b,\,c = k^2,\;(k+1)^2,\;(k+2)^2$$
$$a,\,b,\,c = 2^2,\;k^2,\;(k+1)^2$$
by users coffeemath and martin, respectively, are special cases of the more general solution,
$$a,\,b,\,c = k^2,\;(km\pm1)^2,\;(km\pm2)^2$$
where coffeemath's had $m=1$, while martin's had $k=2,\, m = \frac{n}{2}$.