Theorem: Let $a,b,c$ be positive integers for which $a^n+b^n+c^n$ has at most $k$ distinct prime divisors for all integers $n\ge 1$, for some fixed constant $k$. Then $a=b=c$.
I read from an old thread on AoPS that this result is due to a certain Reutter. I tried to search his name, but I really didn't find anything..
Can you find a refence for the above result?
On
from AOPS in 2004.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
A. March 6, 2004: Let $a,b,c$ be natural numbers (nonzero), such that $a^n + b^n + c^n$ has finite prime divisors, $n=1,2,\ldots$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
G. March 13, 2004, 1:35 PM: Let's assume they aren't equal. Then let $d = \gcd(a,b,c).$ we can obviously work with $a'=a/d,$ $b'=b/d,$ $c'=c/d,$ which are not all equal to $1,$ and $\gcd(a',b',c')=1.$ Let me call $a'=a, b'=b, c'=c$ (for simplicity).
Let $p_i$ be the primes which are the divisors of $$S_n = a^n + b^n + c^n,$$ with $i$ from $1$ to $k.$ Let $$ n_0 = 2 \Pi (p_i - 1). $$ If one of the numbers $a,b,c$ is divisible by $p_i,$ then $$S_{n_0} \equiv 2 \pmod {p_i},$$ and if none of the numbers $a,b,c$ is divisible by $p_i,$ then $$S_{n_0} \equiv 3 \pmod {p_i}.$$ This means that $S_{k n_0}$ is of the form $2^x 3^y$ for all $k \in \mathbf N.$ It's easy to see that it's $2 \pmod 4$ because of the $2$ in front of the product, so it has either the form $2 \cdot 3^x$ or $3^x.$
I'll finish it a bit later, cause my mom wants some time on the computer, so she's rushing me.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
G. March 13, 2004, 6:54 PM: I'll pick up from where I left:
Let $$ A = a^{n_0}. $$ In the same way we get $B$ and $C$ from $b$ and $c$ respectively. We have $$ A^k + B^k + C^k =$$ a power of $3$ for all $k$ or $2 \cdot$ a power of $3$ for all $k.$ Let's assume it's the first one (the second is basically the same).
At the same time, we have $\gcd(A,B,C) = 1.$ This means that at least 2 of $A,B,C$ are coprime with $$ A^t + B^t + C^t, $$ with $t$ chosen such that the sum is greater than $3$ ( such a $t$ exists, because we assume $A,$ $B,$ or $C > 1$), so let's assume those two are $A$ and $B.$ Take $k$ to be $$ k = \phi(A^t + B^t + C^t). $$ If $3|C$ we get $$ A^k + B^k + C^k \equiv 2 \pmod {3^{\mbox{something}}} $$ which is false, and if $3$ does not divide $C,$ we get $$ A^k + B^k + C^k \equiv 3 \pmod {3^{\mbox{something} > 1}} $$ so we have a contradiction again.
I think this ends it.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
P. March 13, 2004, 11:41 PM: Dear G, sorry, maybe I am stupid, but I do not see why $k n_0$ has the form $2^x 3^y.$ Please explain me, cause really this problem take me so long time though the case of two numbers is easy to see! (This is called Reutter theorem)
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
G. March 13, 2004, 11:54 PM: If, for example, $a$ is divisible by $p_i,$ then $b$ and $c$ aren't (we assume $\gcd(a,b,c)=1$), so $$ b^{k n_0} \equiv c^{k n_0} \equiv 1 \pmod {p_i} $$ and $a \equiv 0 \pmod {p_i},$ so $$ S_{k n_0} \equiv 2 \pmod {p_i} $$
If, on the other hand, none of $a,b,c$ are divisible by $p_i$ (this is for a certain $i$ from $1$ to $k$), then $$ a^{k n_0} \equiv b^{k n_0} \equiv c^{k n_0} \equiv 1 \pmod {p_i}, $$ so $$ S_{k n_0} \equiv 3 \pmod {p_i} $$
This means that the remainder of $ S_{k n_0} \pmod {p_i} $ is either $2$ or $3,$ for all $i$ from $1$ to $k.$ If there is a prime divisor of $ S_{k n_0}$ other than $2$ or $3,$ then it can't be among $p_i$ with $i$ from $1$ to $k,$ so the prime divisors of $ S_{k n_0}$ aren't contained in the finite set (this was the initial assumption: that all $S_t$ have their prime divisors in the finite set $$ \{ p_i | 1 \leq i \leq k \}. $$ This shows that the form of $ S_{k n_0}$ is $2^x 3^y.$
Hope it's all correct and clear.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
P. March 15, 2004, 4:26 AM: Well done, G, I think it's correct!
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
On
[Just an attempt to rewrite the above proof, due to grobber]
(Weaker) Claim: Let $a,b,c$ be positive integers. Then the set of prime divisors of $\{a^n+b^n+c^n: n\ge 1\}$ is finite if and only if $a=b=c$.
Proof: The if part is trivial. For the converse, let us suppose without loss of generality that $\text{gcd}(a,b,c)=1$ (in particular, at least one is greater than $1$), define the sequence $(S_n)_{n\ge 1}$ by $S_n:=a^n+b^n+c^n$, and assume by contradition that the set $P$ of primes dividing at least one $S_n$ is finite.
Define $n_0=2\prod_{p \in P}{(p_i-1)}$. Then the factorization of $S_{n_0}$ will have by hypothesis only primes in $P$. In particular, for each prime $p \in P$, at most one integer in $\{a,b,c\}$ can be multiple of $p$. It follows that, for each $p \in P$ and each $k\ge 1$, it holds $S_{kn_0}=a^{kn_0}+b^{kn_0}+c^{kn_0}$ has remainder $2$ or $3$ modulo $p$. But these remainders have to be $0$ modulo some $p \in P$, hence $S_{kn_0}$ will be of the type $2^x 3^y$ for some nonnegative integers $x,y$.
Notice that $n_0$ is even, therefore $S_{kn_0}$ cannot be multiple of $4$, since by assumption $a,b$ and $c$ cannot be all even. Moreover all $\{S_{kn_0}: k\ge 1\}$ have the same parity. Hence they will be all of the type $2\cdot 3^y$ or $3^y$, for some integers $y$. We solve the second case:
We must have $S_{kn_0}$ divides $S_{(k+1)n_0}$ whenever $k$ is sufficiently large. Notice that at least two between $a,b,c$ have to be coprime with $S_{tn_0}$, where $t$ is a sufficiently large fixed positive integer. By construction $S_{tn_0}$ is a power of $3$, let us say $3^q$, with $q\ge 2$. Then $S_{(t-1)n_0}$ has to divide $S_{tn_0}$, which is impossible modulo $9$.
likely this Otmar Reutter, probably no Ph.D., who is quoted in a 1963 issue of Elemente der Mathematik, volume 18, pageS 89-90. Found in SIERPINSKI pages 27-28, 123 at reference 17. At the time, O. Reutter lived in Ochsenhausen, Germany. Maybe the Swiss digital library gives a way to search Elemente for all contributions (including this challenge answer) by him. Or her.
Hmmm. Maybe not. But, maybe once a year, the M.A.A. Monthly lists all the people who answered something in the "Problems and Solutions" column that year. Elemente might do something similar.