For any positive integer $n$, we have the set $P_n = \{ n^k \mid k=0,1,2, \ldots \}$. For positive integers $a,b,c$, we define the group of $(a,b,c)$ as lucky if there is a positive integer $m$ such that $a-1$, $ab-12$, $abc-2015$ (the three numbers need not be different from each other) belong to the set $P_m$. Find the number of lucky groups.
Problem
Source: China Southeast Math Olympiad 2015 Day 1 P4
Tags: number theory
07.06.2017 06:47
By set $a-1=n^k$,we get that there are triple (a,b,c) if and only if there exist n,k,s,t such that : $n^k+1|n^s+12|n^t+2015$ But note that if n is odd,then $n^k+1$ can't divide $n^s+12$,if n is even,$n^s+12$ can't divide $n^t+2015$ So there are no triple (a,b,c)
07.06.2017 08:16
@above an example triple would be $(a,b,c) = (2,1008,1)$.
25.07.2018 16:54
A bit tricky, but still too easy for P4. Let $a-1 = m^x, ab-12 = m^y, abc-2015 = m^z$. Then we obviously have $$m^x+1\mid m^y+12\mid m^z+2015$$Claim 1 : At least one of $x,y,z$ must be zero. Proof : Assume that $x,y,z>0$. Consider numbers $m^x+1, m^y+12, m^z+2015$. If $m$ is odd then these numbers are even, odd, even respectively which contradicts the divisibility condition. On the other hand, if $m$ is even then these numbers are odd, even, odd which also impossible thus the claim must hold. Claim 2 : $z=0$ Proof : If $y=0$, then $m^x+1$ must be $1$ or $13$. Thus $m=12, x=1$ but this will implies that $13 = m^y+12$ will never divides $12^z+2015$, impossible. If $x=0$, then $m^y+12$ must be even. Thus $m$ must be even as well (as $y\ne 0$). But this will imply that $m^z+2015$ must be even too hence $z=0$. Hence Claim 2 is proven. Now we are ready to count. Case 1 : $x=0$. So $2\mid m+12\mid 2016$. Thus the number of solutions is the number of even divisors of $2016$, which is greater than $12$. It's easy to count that the answer is $25$. Case 2 : $x=1$. This implies $m+1\mid m+12\implies m\mid 11$. Both does not satisfies the problem's condition. Case 3 : $x>1$. Since $m$ must be even due to parity reasons, $m^x+1$ must be odd and thus divides $63$. Hence the possible values of $m^x$ are $2, 6, 8, 20, 62$. Hence $(m,x) = (2,3)$. But this will imply $9\mid 2^y+12$ or $3\mid 2^y$, impossible hence no solution. In conclusion, there are $\boxed{25}$ solutions.