For any positive integers $a,b,c,n$, we define $$D_n(a,b,c)=\mathrm{gcd}(a+b+c,a^2+b^2+c^2,a^n+b^n+c^n).$$ 1. Prove that if $n$ is a positive integer not divisible by $3$, then for any positive integer $k$, there exist three integers $a,b,c$ such that $\mathrm{gcd}(a,b,c)=1$, and $D_n(a,b,c)>k$. 2. For any positive integer $n$ divisible by $3$, find all values of $D_n(a,b,c)$, where $a,b,c$ are three positive integers such that $\mathrm{gcd}(a,b,c)=1$.
Problem
Source: 2021 Peru TST D3P2
Tags: number theory, greatest common divisor
06.06.2022 01:49
Let $c=1,b=a^3+a^2-1$ and $a>k$ $a+b+c=a^3+a^2+a=a(a^2+a+1)$ We have $b^n=(a^3+a^2-1)^n \equiv a^{2n} \pmod {a^2+a+1}$ And $a^n+b^n+c^n \equiv a^{2n}+a^n+1 \equiv a^2+a+1 \equiv 0 \pmod{a^2+a+1}$ for $3 \not n$ So $D_n(a,a^3+a^2-1,1)=a^2+a+1>k$ 2.$D_{3n}(a,b,c)=d$ As $(a,b,c)=1$ then $a^2+b^2+c^2 \equiv 1,2,3 \pmod 4$ so $4 \not | d$ $d|(a+b+c)^2+(a^2+b^2+c^2)-2a(a+b+c)=2b^2+2c^2+2bc \to d|2(b^3-c^3)$ Same way we have $2a^3 \equiv 2b^3 \equiv 2c^3 \pmod {d}$ $d|2^n (a^{3n}+b^{3n}+c^{3n}) =(2a^3)^n+(2b^3)^n+(2c^3)^n \to d|3* (2a^3)^n \to d|6*a^{3n}$ If $(d,a)=t>1$ then $t|b+c, t|b^2+c^2 \to t| (b+c)^2-(b^2+c^2)-2b(b+c)=-2b^2$ if $(t,b)>1$ then $t|c$ so $(a,b,c)>1 \to$ contradiction. So $(d,a)=1,2$ But then $d| 6$ And we have $D_{3n}(3,1,1)=1,D_{3n}(2,1,1)=2, D_{3n}(1,1,1)=3,D_{3n}(4,1,1)=6$
06.06.2022 02:00
Superb NT. Here is a less slick solution. 1. Let $p\equiv 1\pmod{6}$ a prime. I claim (a) there exists $a,b,c$ such that $(a,b,c)=1$, $a^3\equiv b^3\equiv c^3\pmod{p}$ and $a,b,c$ are distinct modulo $p$; and (b) $p\mid D_n$ for any such triple. I first show (a). Let $k$ be a cubic root modulo $p$, $g$ be a primitive root with $g^{3i}\equiv k\pmod{p}$ for some $i$. Note that if \[ a\equiv g^i\pmod{p}, \quad b\equiv g^{i+\frac{p-1}{3}}\pmod{p}\quad\text{and}\quad c\equiv g^{i+2\frac{p-1}{3}}\pmod{p}. \]Clearly $a^3\equiv b^3\equiv c^3\pmod{p}$ ad they are all distinct as $g$ is a primitive root. Finally, ensuring $(a,b,c)=1$ is simple: just select $c\equiv 1\pmod{a}$ and we are done as $(a,b,c)\mid (a,c)=1$. This shows Claim (a). Now claim (b): note that if $a^3\equiv b^3\equiv c^3\pmod{p}$ then $p\mid (a-b)(a^2+ab+b^2)$. As $p\nmid a-b$, we get $p\mid a^2+ab+b^2$. Likewise, $p\mid b^2+bc+c^2$ and $p\mid c^2+ca+a^2$. Subtract the second from first to get $p\mid (a-c)(a+b+c)$ yielding $p\mid a+b+c$. Moreover, summing them up we get $p\mid 3(a^2+b^2+c^2)+(ab+bc+ca)$. This, together with $p\mid 3(a+b+c)^2 =3(a^2+b^2+c^2)+6(ab+bc+ca)$ yields $p\mid 5(ab+bc+ca)$, hence $p\mid ab+bc+ca$. In particular, $p\mid a^2+b^2+c^2$. Finally, if $n=3\ell+1$ and $a^3\equiv b^3\equiv c^3\equiv k\pmod{p}$ then $a^n+b^n+c^\equiv k^\ell(a+b+c)\equiv 0\pmod{p}$, analogously for $n=3\ell+2$. This establishes Claim (b), thus part 1. 2. Note that $D_n\mid (a+b+c)^2 - (a^2+b^2+c^2)$, yielding $D_n\mid 2(ab+bc+ca)$. Now if $2\mid D_n$ then two of $a,b,c$ are odd and one is even, thus $a^2+b^2+c^2\equiv 2\pmod{4}$. Consequently, $v_2(D_n)\le 1$. Next, take any odd divisor $d$ of $D_n$. Then $d\mid ab+bc+ca$. Using $c\equiv -(a+b)\pmod{d}$, we get $d\mid a^2+ab+b^2$. This, in turn, yields $a^3\equiv b^3\equiv c^3\equiv k\pmod{d}$. Note also that $(d,a)=(d,b)=(d,c)=1$ as otherwise if $q\mid (d,a)$ a prime then $q\mid b,c$, contradiction. Finally as $n=3\ell$ for some $\ell$, we get $a^n+b^n+c^n\equiv 3k^\ell\pmod{d}$, thus $d\mid 3$. From here, we get $D_n\mid 6$. It is easy to see $D_n(3,1,1)=1$, $D_n=(1,1,1)=3$, $D_n=(2,1,1)=2$ and $D_n(4,1,1)=6$.