Let $g(n)$ be the greatest common divisor of $n$ and $2015$. Find the number of triples $(a,b,c)$ which satisfies the following two conditions: $1)$ $a,b,c \in$ {$1,2,...,2015$}; $2)$ $g(a),g(b),g(c),g(a+b),g(b+c),g(c+a),g(a+b+c)$ are pairwise distinct.
Problem
Source: CGMO 2015 Q4
Tags: number theory, greatest common divisor
03.03.2016 03:15
Is the answer $138240$
18.08.2016 18:50
We generalise for $n=pqr$ with $p,q,r$ distinct odd primes. If any prime divide two elements of one of the following sets, it divide the third. $$\{a,\,b+c,\,a+b+c\}\,,\;\{b,\,a+c,\,a+b+c\}\,,\;\{c,\,a+b,\,a+b+c\}\,,$$$$\{b,\,b+c,\,c\}\quad\quad,\quad\quad\{c,\,c+a,\,a\}\quad\quad,\quad\quad\;\{a,\,a+b,\,b\}$$Hence, if $pqr\mid x_1$ (i.e. $g(x_1)=pqr$), then $p$ (resp. $q,r$)$\mid x_2\iff p$ (resp. $q,r$) $\mid x_3$ and so $g(x_2)=g(x_3)$. Contradiction. We have $$\{g(a),\,g(b),\,g(c),\,g(a+b),\,g(b+c),\,g(c+a),\,g(a+b+c)\}=\{1,\,p,\,q,\,r,\,pq,\,qr,\,rp\}$$Each prime divide exactly 3 elements. Suppose $p\mid x,y,z$. $\bullet$ If $\{x,\,y,\,z\}=\{a+b,\,b+c,\,c+a\}\implies p\mid 2(a+b+c)\implies p\mid a+b+c$ hence $p$ divide at least 4 elements. Contradiction. $\bullet$ Otherwise $\{x,\,y,\,z\}$ share at least two elements with one of the above sets. Hence $\{x,\,y,\,z\}$ is one of the above 6 sets. So we assign a set for each prime. If two primes $p,q$ 'divide' the same set, we have $pq\mid x,y,z\implies\{g(x),g(y),g(z)\}\subseteq\{pq\}$. Contradiction. A valid assignment is an ordered triple $(S_p,S_q,S_r)$ of distinct set with $S_p\cap S_q\cap S_r=\emptyset$. There are $A_6^3-4\cdot 3!$ such assignement. Let's fix an assignment. $\bullet$ Either $S_p=\{a,b+c,a+b+c\}\iff a\equiv0\wedge b\equiv-c\not\equiv0\pmod p$ : $p-1$ choices modulo $p$. $\bullet$ Either $S_p=\{a,a+b,b\}\iff a\equiv b\equiv0\wedge c\not\equiv0\pmod p$ : $p-1$ choices modulo $p$. Now, using CRT, any of the $(p-1)(q-1)(r-1)$ choices of $(a,b,c)$ modulo $p$,$q$ and $r$ match with a choice of $(a,b,c)\in[\![1,pqr]\!]^3$. Finally, there are $$\mathcal{N} = (A_6^3-4\cdot 3!)\cdot(p-1)(q-1)(r-1)=96\cdot(p-1)(q-1)(r-1) = 138\,240$$Such triples.