Do there exist infinitely many triples of positive integers $(a, b, c)$ such that $a$, $b$, $c$ are pairwise coprime, and $a! + b! + c!$ is divisible by $a^2 + b^2 + c^2$? Proposed by Anzo Teh Zhao Yang
Problem
Source: Malaysian IMO TST 2023 P4
Tags: number theory
30.04.2023 13:48
This is just an idea. There are infinitely many primitive pythagorean triplets, write $a = m^2-n^2$, $b = 2mn$ and $c = m^2+n^2$, with $m,n$ positive integers with $m,n$ coprime and one even. Take $c$ a prime number $p$, there are infinitely many prime numbers that can be written as a sum of two squares. We want $a^2+b^2+c^2 = 2c^2 = 2p^2|a!+b!+p!$. Therefore, if we can find infinitely many $a,b$ such that $a!+b! \equiv p \pmod{p^2}$, and $a^2+b^2 = p^2$ we are done. I don't have any ideas to finish this however.
30.04.2023 13:53
Here's a super dumb solution: The answer is yes. Take $a=k^2+3,b=2k^2+5,c=k^2+k+2$. Note that $a^2+b^2+c^2=((k^2+2)+1)^2+(2(k^2+2)+1)^2+((k^2+2)+k)^2 \equiv 0 \pmod {k^2+2},$ and so we may factorize: $a^2+b^2+c^2=(k^2+2)(6k^2+2k+19)$. It is easy to verify that $\gcd(k^2+2,6k^2+2k+19)=1$ for infinitely many $k$, and that $6k^2+2k+19$ is not divisible by $2,3,5$ or $7$ for infinitely many $k$, too. For example, we may take $k$ such that $3 \cdot 5 \cdot 7 \cdot 19 \mid k$. Then, $2 \cdot 3 \cdot 5 \cdot 7 \mid (6k^2+2k)$, and so $\gcd(6k^2+2k+19,2 \cdot 3 \cdot 5 \cdot 7)=1$, and moreover if $p \mid (k^2+2)$ and $p \mid (6k^2+2k+19)$ for some prime $p$, then $2k+7 \equiv 2k+(6k^2+19) \equiv 0 \pmod d,$ and so $0 \equiv 2k^2+4 \equiv -7k+4 \pmod d,$ that is $d \mid (14k-8)$ and $d \mid 7(2k+7)=14k+49$, hence $d \mid (14k+49)-(14k-8)=57=3 \cdot 19$. If $p=3$, then $ 3 \mid (6k^2+2k+19)$, and so $k \equiv 1 \pmod 3,$ a contradiction. If $p=19$, then $19 \mid k^2+2$, and so $19 \mid 2$, again a contradiction. Now, we are almost done. Since $k^2+2 < \min \{a,b,c \}$, we conclude that $a!+b!+c!$ is a multiple of $k^2+2$. Now, in order to handle $6k^2+2k+19$, we will furthermore assume that $k \equiv -1 \pmod {23}$ and $k \equiv 4 \pmod {41}$. Then, it is easy to see that $23 \cdot 41 \mid (6k^2+2k+19)$, hence if we write $6k^2+2k+19=23^a \cdot 41^b \cdot d$ with $\gcd(d,23 \cdot 41)=1$, then $23^a<k^2$, since otherwise $6k^2+2k+19 \geq 23^a \cdot 41^b \geq 41k^2,$ a contradiction. Similarly, $41^b<k^2$, and $d \leq k^2$. Thus, $23^a, 41^b, d$ are all less than $k^2$, and so divide $a!+b!+c!$. Since they are coprime, their product does so, too. Hence, we are done. To sum up, we need that $k$ satisfies $3 \cdot 5 \cdot 7 \cdot 19 \mid k$, and $k \equiv -1 \pmod {23}$, $k \equiv 4 \pmod {41}$, which can easily be realized using CRT.
16.07.2023 20:29
Let $a=x^3+18, b=x^3, c=x^3-18$. I will prove that these triple work for infinitely many values of $x$. In fact take $x=(k^4-6k^2+36)/4-k$ where $k$ is a positive integer. Let $k=2m$. Then $x=4m^4-6m^2-2m+9$. Take also $m \equiv 1 (mod 3)$. Then it is trivial to show that $gcd(x,2)=gcd(x,3)=1$, hence $a,b,c$ are coprime. Now we will prove that $a^2+b^2+c^2$ divides $(x^3-18)!=c!$, which is enough as $c=min(a,b,c)$ We have that: $a^2+b^2+c^2=(x^3+18)^2+(x^3)^2+(x^3-18)^2=3(x^2+6)(x^4-6x^2+36)$ For large enough $x$ we have that $x^3-18>3(x^2+6)$, hence $3(x^2+6)$ divides $(x^3-18)!$ Also $gcd(x,2)=gcd(x,3)=1$ yields that $gcd(3(x^2+6),x^4-6x^2+36)=1$ So it remains to prove that $x^4-6x^2+36$ divides $(x^3-18)!$ for infinitely many $x$ of the above form. By definition of $x$ we have that $x+k$ divides $k^4-6k^2+36$, so it must also divide $x^4-6x^2+36$. Let $x^4-6x^2+36=A(x+k) (1)$. Then $A=(x^4-6x^2+36)/(x+k)<(x^4-6x^2+36)/x<x^3-18$ for large enough $x$. Also for large enough $k$ we have that $x>k=>x+k<2x<x^3-18$ for large $x$. So, (1) gives that $x^4-6x^2+36$ is a product of two numbers which are $<x^3-18$. So if a prime divides $x^4-6x^2+36$, then it must be less than $x^3-18$. Now take a prime $p$ dividing $x^4-6x^2+36$ such that $p<x^2$. Then by Legendre formula: $v_p((x^3-18)!)>(x^3-18)/p-1>(x^3-18)/x^2-1>x-2$ for large enough $x$. Also for large $x: p^{x-2} \geq 2^{x-2}>x^4-6x^2+36$, so $v_p(x^4-6x^2+36)<x-2<v_p((x^3-18)!)$ Now take a prime $r$ dividing $x^4-6x^2+36$ such that $x^2<r<x^3-18$. Then $r$ obviously divides $(x^3-18)!$ and for large enough $x$ we get that $r^2>x^4>x^4-6x^2+36$, so $v_r(x^4-6x^2+36) \leq 1 \leq v_r((x^3-18)!)$ So, in fact, we proved that $v_p(x^4-6x^2+36) \leq v_p((x^3-18)!)$ for all prime divisors of $x^4-6x^2+36$, from where we conclude that $x^4-6x^2+36$ divides $(x^3-18)!$ as needed
13.10.2023 10:12
Official Solution: Solution 1: We show that there exist infinitely many triples $(k, a, b)$ such that: Indeed, we first show that such positive integers $(a, b)$ exist for all $k\ge 2$ if we do not impose the constraint $a, b\ge 10k$. For $k = 2$, we have $24^2 + 7^2 = 25^2$. Next, suppose that for some $k$ we have $a_k^2+b_k^2 = 5^{2k}$, and neither $a_k$ nor $b_k$ is divisible by 5. Consider, now, the following: \[ (3a_k + 4b_k) ^2 + (4a_k - 3b_k)^2 = 25(a_k^2 + b_k^2) = 5^{2(k + 1)} \]\[ (3a_k - 4b_k) ^2 + (4a_k + 3b_k)^2 = 25(a_k^2 + b_k^2) = 5^{2(k + 1)} \]In addition, given that $5\nmid a_k$ and $5\nmid b_k$, $3a_k + 4b_k$ and $3a_k - 4b_k$ cannot be both divisible by 5. Thus w.l.o.g. suppose that $5\nmid 3a_k + 4b_k$, then $5\nmid 4a_k - 3b_k$ either (since the sum of squares is divisible by 5). We may then take $a_{k+1} = 3a_k + 4b_k$ and $b_{k+1} = |4a_k - 3b_k|$. Now consider $(a_k, b_k)$ as the pairs we have chosen for each $k$. We now show that for sufficiently large $k$, either both $a_k, b_k\ge 10k$, or both $a_{k+1}, b_{k+1}\ge 10(k + 1)$. Consider $k\ge 100$: for these $k$, we have $5^{2k} > 10^9k$. Suppose that $b_k < 10k$. Then $a_k = \sqrt{5^{2k} - a_k^2} > \sqrt{10^9k - 100k} > 10^4k$. Recall that $(a_{k+1}, b_{k+1})$ are either $(3a_k + 4b_k, |4a_k - 3b_k|)$ or $(|3a_k - 4b_k|, 4a_k + 3b_k)$. This means that both $a_{k+1}, b_{k+1}$ are at least \[\min\{|3a_k - 4b_k|, |4a_k - 3b_k|\}> \min\{3(10^4k) - 4(10k), 4(10^4k) - 3(10k)\} > 2(10^4k) > 10(k + 1). \]Now to finish the solution, choose all those $(k, a_k, b_k)$ (with $k\ge 2$) satisfying the condition above, and $c_k=5^k$. Then $a_k^2 + b_k^2 + c_k^2 = 2\cdot 5^{2k}$. Denote $\nu_p(k)$ as the highest power of prime $p$ dividing $k$. Since $a_k, b_k, c_k\ge 10k$, we have $\nu_5(a_k!), \nu_5(b_k!), \nu_5(c_k!)$ all $\ge 2k$. This means $a_k! + b_k! + c_k!$ is divisible by $5^{2k}$. Also $a_k, b_k, c_k > 1$ means their factorials are even, hence $2\mid a_k! + b_k! + c_k!$. Finally, the only prime divisor of $c_k$ is 5, and the only prime divisor of $a_k^2+b_k^2$ is 5, but neither $a_k, b_k$ is divisible by 5. This gives $(a_k, b_k, c_k)$ a valid triple. $\blacksquare$ Solution 2: We give the same construction, with a simpler proof on the bounds for the last condition. Suppose we have found some $a, b$ satisfying $a^2 + b^2 = 5^{2k}$, then simply note that for all $k\ge 5$, $$a^2=5^{2k}-b^2\ge 5^{2k}-(5^k-1)^2=2\cdot 5^k-1>100k^2 \Rightarrow a\ge 10k$$Likewise $b\ge 10k$ too. $\blacksquare$ Remark 1: One may also ask what happens as we replace $a^2 + b^2 + c^2$ with $a^n + b^n + c^n$ for $n > 2$. The proposer believes that this will increase the problem difficulty significantly (even for the easier variant on $n=3$) given that we know very little on sum of $n$-th power (beyond Fermat's Last Theorem). Remark 2: One may also consider the easier variant as follows: Do there exist infinitely many triples of positive integers $(a, b, c)$ such that $a$, $b$, $c$ are pairwise coprime, and $a!b!c!$ is divisible by $a^2 + b^2 + c^2$? We note that our construction also works for the easier variant. In fact, the easier variant admits an easier construction: Consider any prime $p$ in the form $4k+1$, then there is $a^2+b^2=p$ for some $(a, b)$. Choose $c = p$, then $a^2+b^2+c^2=p(p + 1)$. Note that both $p$ and $p + 1$ divide $p!$ since $p + 1$ is composite. In fact, the construction $c=a^2+b^2$ works whenever $\gcd(a, b) = 1$ and $a^2+b^2+1$ is not prime.
13.10.2023 14:40
We may choose $(a,b,c)=(x,x+3,x+9)$. We will prove that this construction works for infinitely many $x$. Clearly, to satisfy the coprime condition, we will require $gcd(x,6)=1$. We will now try to show that $a^2+b^2+c^2|x!|x!+(x+3)!+(x+9)!$ Now, notice $$a^2+b^2+c^2=3x^2+24x+90=3(x^2+6x+30)$$So for $x\geq 3$, $v_3(a^2+b^2+c^2)\leq v_3(x!)$. Also notice $x^2+6x+30$ has no factor of 3($gcd(x,3)=1$). So hence for all $x\geq 3$, we only need $x^2+8x+30|x!$. Now we shall note that $$x^2+8x+30=(x+7)^2-(6x+19)$$Naturally, we would hope for $6x+19$ to be a square number(note we do not choose $(x+6)^2$ as this would not form any squares, a similar reason for not choosing $(x,x+3,x+6)$). Suppose $k^2=6x+19$, then $x^2+8x+30=(x+7-k)(x+7+k)$. We wish that some prime divides $x+7+k$. Hence we will find $k$ such that $x+7+k$ is a multiple of $p>3$. $$p|x+7+k \iff p| \frac{6x+19+23}{6}+k \iff p| \frac{k^2+6k+23}{6} \iff p| k^2+6k+23 $$One can easily find a suitable $p$, $5$ when $k=1\mod{5}$. $x+7+k$ is only equal to $5(x+7-k)$ at most once, so we can just remove that $x$ if it exists. If $x$ is large enough, $5,\frac{x+7+k}{5},x+7-k$ are distinct. So then since these are all $<x$, they multiplied together will be a factor of $x!$. Hence it suffices to prove there are infinitely many such $x,k$. We choose $k>1$ such that $k\equiv 1 \mod{5}, k\equiv 2\mod{9}, k\equiv 1 \mod{4}$. Then, $$6x = k^2-19 \equiv 2 \mod{4} \implies x\equiv 1\mod{2}$$and $$6x = k^2-19 \equiv 3 \mod{9} \implies x\equiv 2 \mod{3}$$Hence $gcd(x,6)=1$. Also, $x+7+k\equiv k^2+6k+23\equiv 30 \equiv 0\mod{5}$ which was already stated before. Hence $x=\frac{k^2-19}{6}$ will work for all such $k$
18.02.2024 15:08
An alternative solution. The Pell(ish) equation $5m^2=4k^2+1$ has infinitely many solutions in positive integers. So, there are infinitely many $(m,k)$ solutions such that $m>20$. Take one such pair. Combined with the fact that $k>m$, we have $25m^4|\ 5.10.15.20.m.2m.3m.4m|\ (4m)!|\ (4k)! \ $. $\implies (4k^2+1)^2|(4k)!$ We also have $2|(4k)!$. Since $(2,4k^2+1)=1, \ \ 2(4k^2+1)^2|\ (4k)! | \ (4k^2-1)! + (4k^2+1) + (4k)!$. Now, we can take $(a,b,c)=(4k^2-1,4k,4k^2+1)$. Because of the arguments above, this triple satisfies the given conditions.