Determine all the triples $\{a, b, c \}$ of positive integers coprime (not necessarily pairwise prime) such that $a + b + c$ simultaneously divides the three numbers $a^{12} + b^{12}+ c^{12}$, $ a^{23} + b^{23} + c^{23} $ and $ a^{11004} + b^{11004} + c^{11004}$
Problem
Source: Rioplatense Olympiad 2018 level 3 p3
Tags: number theory, coprime, coprime numbers, Sum of powers, divides
14.12.2018 01:12
Here is a bad solution, which can't be done in competition due to heavy computation. I hope someone posts nice solution. Let $ I=\left( x+y+z,x^{12} +y^{12} +z^{12} ,x^{23} +y^{23} +z^{23}\right)$ be an ideal of $ \mathbb{Z}[ x,y,z]$. By computing a Gröbner basis of $ I$ with lexicographical ordering, we can verify that $ 94254\cdotp z^{33} \in I$. So we have $ d:=\gcd\left( a+b+c,a^{12} +b^{12} +c^{12} ,a^{23} +b^{23} +c^{23}\right) \mid 94254\cdotp c^{33}$ First, we will show that $ d\mid 94254$. (In fact, we can find $ ( a,b,c) \in \mathbb{Z}^{3}_{+}$ such that $ d=94254$) Let $ p$ be an arbitrary prime for which $ p\mid d$ and $ p\mid c$. Then we have $ p\mid a+b$ and $ p\mid a^{12} +b^{12}$ , which implies $ p\mid 2a^{12}$. So it follows from $ \gcd( a,b,c) =1$ that $ p=2$. Assume that $ 4\mid d$. We have $ 4\mid a^{12} +b^{12} +c^{12}$, which implies $ a\equiv b\equiv c\equiv 0\pmod 2$. So it follows from $ \gcd( a,b,c) =1$ that $ 4\nmid d$. Thus, $ d$ is a positive divisor of $ 94254=2\cdotp 3\cdotp 23\cdotp 683$. For simplicity, let $ k=11004$. Let $ p$ be an prime divisor of $ \gcd\left( d,a^{k} +b^{k} +c^{k}\right)$. Since $ \gcd( a,b,c) =1$, there exist $ ( s,t) \in \mathbb{Z}^{2}$ for which $ s+t+1\equiv s^{12} +t^{12} +1\equiv s^{k} +t^{k} +1\equiv 0\pmod p$ implying that $s^{12} +( s+1)^{12} +1\equiv s^{k} +( s+1)^{k} +1\equiv 0\pmod p$ ...$ ( \heartsuit )$ By solving congruence equation $ x^{12} +( x+1)^{12} +1\equiv 0\pmod p$, we can verify that $ ( \heartsuit )$ cannot be hold for $ p\in \{23,683\}$. Therefore, $ \gcd\left( a+b+c,a^{12} +b^{12} +c^{12} ,a^{23} +b^{23} +c^{23} ,a^{k} +b^{k} +c^{k}\right) \mid 6$. So if $ a+b+c\mid a^{12} +b^{12} +c^{12} ,a^{23} +b^{23} +c^{23} ,a^{k} +b^{k} +c^{k}$, then $ a+b+c\mid 6$. From here, we can easily conclude that the only solution are $(a,b,c) =( 1,1,1) ,( 4,1,1) ,( 1,4,1) ,( 1,1,4)$.
28.02.2019 02:55
First, some easy observations: 1. If $4|a+b+c$, then 2 of $a,b,c$ are odd (say $a,b$), and $4|a+b+c|a^{12}+b^{12}+c^{12}$. However, $a^{12}+b^{12}+c^{12} = (a^2)^6+(b^2)^6+(c^2)^6\equiv 1^6+1^6+0^6 \equiv 2 \text{ (mod }4)$, which is an absurd. Therefore, $v_2(a+b+c) \le 1$. 2. If $9|a+b+c$, then 2 or 3 of $a,b,c$ are not multiple of 3, and $9|a+b+c|a^{12}+b^{12}+c^{12}$. However, $a^{12}+b^{12}+c^{12} = (a^6)^2+(b^6)^2+(c^6)^2 \equiv 2, 3 \text{ (mod }9)$, which is an absurd. Therefore, $v_3(a+b+c) \le 1$. 3. If $p>2$ is a prime factor of $a+b+c$, then $(a,p)=(b,p)=(c,p)=1$, because if not (let's say $p|a$), we have $b\equiv -c \text{ (mod }p) \Rightarrow b^{12} \equiv c^{12} \text{ (mod }p)$. This, together with $p|a+b+c|a^{12}+b^{12}+c^{12}$, gives $p|2b^{12}\Rightarrow p|b$ and $p|c$, and therefore $p|(a,b,c)$, contradiction. Suppose now that exists a prime $p>3$ such that $p|a+b+c$. By the condition of the problem, we have $a^{n}+b^{n}+c^{n} \equiv 0 \text{ (mod }p)...(*)$, for $n=1,12,23,11004$. In the following, all congruences are modulo $p$. Setting $n=1$ in $(*)$, $c\equiv -(a+b)$. Setting $n=12$ in $(*)$, $-c^{12} \equiv -(a+b)^{12} \equiv a^{12}+b^{12}$, and if we divide by $b^{12}$ and set $x=ab^-1$ (inverse modulo $p$), we have $x^{12}+1\equiv -(x+1)^{12}...(1)$. In a similar way, if we set $n=23$ in $(*)$, $ -c^{23} \equiv (a+b)^{23} \equiv a^{23}+b^{23}$, and if we divide by $b^{23}$, we have $(x+1)^{23} \equiv x^{23}+1...(2)$. From $(1),(2)$, $(x^{12} + 1)^2 \equiv (x+1)^{24} \equiv (x+1)^{23}(x+1) \equiv (x^{23}+1)(x+1)$, then $x^{24} +2x^{12}+1\equiv x^{24}+x^{23}+x+1 \Rightarrow x(x^{11}-1)^2 \equiv 0$. Since $x$ is not multiple of $p$, we conclude that $x^{11} \equiv 1$, or $a^{11} \equiv b^{11}$. Analogously, $b^{11} \equiv c^{11}$, and since $11004 = 11\cdot 1000 + 4$, setting $n=11004$ in $(*)$, $0 \equiv a^{11004}+b^{11004}+c^{11004} \equiv a^{11000}(a^4+b^4+c^4) \Rightarrow 0\equiv a^4+b^4+c^4$, so $(*)$ is valid for $n=4$ as well. Therefore, $-c^4 \equiv -(a+b)^4 \equiv a^4 +b^4$ and if we divide by $b^{4}$, we have $-(x+1)^{4} \equiv x^{4}+1...(3)$. From $(1)$ and $(3)$, $-(x^4+1)^3 \equiv (x+1)^{12} \equiv -(x^{12}+1) \Rightarrow x^{12}+3x^4(x^4+1)+1 \equiv x^{12}+1 \Rightarrow 3x^4(x^4+1) \equiv 0$. Since $3,x$ are not multiples of $p$, $x^4 \equiv -1 \Rightarrow x^{12} \equiv -1 \equiv x$. But $x^4 \equiv (-1)^4 \equiv 1 \equiv -1$, so $2\equiv 0 $ and $p=2$, contradiction. Therefore, the only primes dividing $a+b+c$ are 2 and 3, and from the easy observations, we conclude that $a+b+c=3$ or $a+b+c=6$. The first case implies $a=b=c=1$, which is clearly a solution, and the second case implies $\{ a,b,c \}=\{ 1,2,3 \}$ (invalid, because $6|1^{12}+2^{12}+3^{12}$ is false, just look modulo 3) ou $\{ a,b,c \} = \{ 1,1, 4 \}$, which is indeed a solution ($1^n+1^n+4^n \equiv 2 \equiv 0 \text{ (mod }2)$ and $1^n +1^n +4^n \equiv 1+1+1 \equiv 0 \text{ (mod }3)$). Conclusion: $(a,b,c)=(1,1,1),(1,1,4),(1,4,1),(4,1,1)$.