Find all triples $(a,b,c)$ of positive integers such that if $n$ is not divisible by any prime less than $2014$, then $n+c$ divides $a^n+b^n+n$. Proposed by Evan Chen
Problem
Source: ELMO 2014 Shortlist N7, by Evan Chen
Tags: number theory, number theory proposed, Hi
25.07.2014 14:16
This problem is seriously misplaced, unless I have made a major blunder in my solution. I'll just give a very brief outline as the details are somewhat boring. Firstly, assume $c$ is even. We use CRT and Dirichlet to show that there are infinitely many primes $p$ such that $n=p-c$ is not divisible by any prime less than $2014$. Then the divisibility condition becomes, after using Fermat's Little Theorem, $p | ab^c + ba^c - ca^c b^c$. This last expression must equal $0$ as it is divisible by infinitely many primes $p$ and we then finish by easy bounding etc. In the case where $c$ is odd, we show, using similar methods as above, that we can find infinitely many primes $p$ such that $n=2p-c$ is not divisible by any prime less than $2014$. Then we obtain $p| a^2b^c+b^2a^c-ca^cb^c$. This expression equals $0$ and we finish by bounding again. The unique triple is $(1, 1, 2)$.
21.12.2014 23:32
This is misplaced in the literal sense of the word. It should actually be ELMO Shortlist N4!
23.04.2015 22:56
My solution: Let $S$ be the product of all prime numbers less than $2014$. From Dirichlet's Theorem there are infinitely prime numbers $p$ such that $p\equiv 1\pmod{s}$. Using Chinese remainder theorem there exist a natural number $n$ such that $n\equiv -c\pmod{p},n\equiv 1\pmod{p-1}$ note that for some $m\in\mathbb{N}: n=m(p-1)+1\longrightarrow (n,p-1)=1\Longrightarrow (n,S)=1$. from ferma's little theorem we get: $p\mid n+c\mid a^n+b^n+n\equiv a+b-c\Longrightarrow a+b=c (\bigstar)$ (because $p$ is large enough) now take an arbitrary prime number $q>2015$ then by chinese remainder theorem there is a natural number $t$ such that $t\equiv -c\pmod{p},t\equiv q\pmod{p-1}\Longrightarrow (t,S)=1$ hence: $p\mid t+c\mid a^t+b^t+t\equiv a^q+b^q-c\pmod{p}\Longrightarrow a^q+b^q=c (\bigstar\bigstar)$ (because $p$ is arbitrary large and $q$ is a fixed number) from $(\bigstar) , (\bigstar\bigstar)$ we get $a=b=1,c=2$. Q.E.D
28.09.2015 03:14
A nice problem, well although it succumbs to a bit of advancements like Weak Dirichlet with a touch of CRT, It is evident that without sufficient machinery, it is not at all trivial rather way too hard in my opinion without weak Dirichlet. Anyway, here it is: Let $p$ be a prime.(We will make a good choice for $p$ a bit later.) Let $n \equiv -c \bmod p$ $n \equiv 1 \bmod (p-1)$. Then clearly, $p \mid n+c \mid a^n+b^n-c$ and so $p\mid a+b-c$. (By using FLT). For sufficiently large primes $p$ this fails unless $a+b=c$. Now to make sure we did not mess up somewhere, i.e., $n$ is not divisible by any prime less than $2014$, let $p_1(=2),p_2,...,p_k$ be all the primes less than $2014$. Set $p \equiv 1 \bmod p_i$ $\forall 1\le i\le k$. (which by Weak Dirichlet is guaranteed to exist.) Thereafter, choose a prime $q$ such that $n \equiv -c \bmod q$ $n \equiv -1 \bmod (q-1)$ $q \equiv 1 \bmod p_i$ $\forall 1\le i\le k$ This shall give $\frac{1}{a} +\frac{1}{b} -c \equiv 0 \bmod q$ This implies $ q \mid a+b-abc $ But, by Weak Dirichlet, infinitely many such $q$ are guaranteed, so this fails for sufficiently large $q$ unless $a+b=abc=ab(a+b)$. So the only solutions are $(a,b,c)=(1,1,2)$. (Note :- Clearly, CRT guarantees the existence of such an $n$.) P.S.- I might have missed something( i usually mess up) Please help me correct if anything of this sort happens.
05.10.2015 22:36
andria wrote: my solution: take every prime $p>max\{a,b,c\}$ then using Chinese remainder theorem there exist a natural number $n$ such that $n\equiv -c\pmod{p}$, $n\equiv 0\pmod{p-1}$ You can't assume that $n\equiv 0\pmod{p-1}$ because that would mean $2|n$.
09.04.2019 15:19
Quote: This is misplaced in the literal sense of the word. It should actually be ELMO Shortlist N4! From my perspective, it IS ELMO Shortlist N4!
10.03.2020 17:26
Nice! Here's my solution: The only such triplet is $(a,b,c)=(1,1,2)$, which trivially works. Now we show there are no other solutions. Let $p_1,p_2, \dots ,p_k$ denote the set of primes less than $2014$, and suppose $P=p_1p_2 \dots p_k$. We break into two cases based on the parity of $c$. CASE 1 ($c$ is even) Note that, for any $1 \leq i \leq k$, we cannot have $p_i \mid c+1$ and $p_i \mid c-1$ simultaneously. Let $x$ be a positive integer such that $x \equiv c+1 \pmod{p_i}$ for every $i$ such that $p_i \nmid c+1$, and $x \equiv c-1 \pmod{p_j}$ if $p_j \mid c+1$ ($x$ exists by CRT). Then $\text{gcd}(x,P)=1$, and so there are infinitely many primes $q$ of the form $mP+x$ for $m \in \mathbb{N}$ (by Dirichlet's Theorem). Choose such a prime $q$ greater than $a+b+c$. By our construction, we have $\text{gcd}(q-c,P)=1$. Taking $n=q-c$, we get $$q \mid a^{q-c}+b^{q-c}+q-c \Rightarrow a^{q-c}+b^{q-c} \equiv c \pmod{q}$$$$\Rightarrow a^{c-1}+b^{c-1} \equiv a^{q-1}b^{c-1}+b^{q-1}a^{c-1} \equiv c(ab)^{c-1} \pmod{q}$$Since $q \mid a^{c-1}+b^{c-1}-c(ab)^{c-1}$, so in fact we must have $a^{c-1}+b^{c-1}=c(ab)^{c-1}$. Note that $c$ is even, and so $c \geq 2$. For $a=1$, we have $$b^{c-1}+1=cb^{c-1} \geq 2b^{c-1} \Rightarrow b^{c-1} \leq 1 \Rightarrow b=1 \Rightarrow (a,b,c)=(1,1,2)$$We get the same solution for $b=1$. So WLOG assume $a \geq b \geq 2$. Then $$c(ab)^{c-1}=a^{c-1}+b^{c-1} \leq 2a^{c-1} \Rightarrow 2 \geq cb^{c-1} \geq 2 \times 2^{c-1} \Rightarrow c=1 \rightarrow \text{Contradiction!}$$ CASE 2 ($c$ is odd) We claim that there are infinitely many primes $q>a+b+c$ such that $\text{gcd}(2q-c,P)=1$. First assume $c=1$. Choose a prime $q$ of the form $mP+1$ such that $q>a+b+c$ (which exists by Dirichlet's Theorem). Then $\text{gcd}(2q-c,P)=1$, as desired. Now suppose $c \geq 3$. Note that, for any $1 \leq i \leq k$, we cannot have $p_i \mid \frac{c+1}{2}$ and $p_i \mid \frac{c-1}{2}$ simultaneously. Let $x$ be a positive integer such that $x \equiv \frac{c+1}{2} \pmod{p_i}$ for every $i$ such that $p_i \nmid \frac{c+1}{2}$, and $x \equiv \frac{c-1}{2} \pmod{p_j}$ if $p_j \mid \frac{c+1}{2}$ ($x$ exists by CRT). Then $\text{gcd}(x,P)=1$, and so there are infinitely many primes $q$ of the form $mP+x$ for $m \in \mathbb{N}$ (by Dirichlet's Theorem). Choose such a prime $q$ greater than $a+b+c$. By our construction, we have $\text{gcd}(2q-c,P)=1$. Now, take $n=2q-c$ (for prime $q$ given above). Then we get $$q \mid n+c \mid a^{2q-c}+b^{2q-c}+2q-c \Rightarrow a^{2q-c}+b^{2q-c} \equiv c \pmod{q}$$$$\Rightarrow a^{c-2}+b^{c-2} \equiv a^{2(q-1)}b^{c-2}+b^{2(q-1)}a^{c-2} \equiv c(ab)^{c-2} \pmod{q}$$Since $q \mid a^{c-2}+b^{c-2}-c(ab)^{c-2}$, so in fact we must have $a^{c-2}+b^{c-2}=c(ab)^{c-2}$. For $c=1$, we get $a+b=1$, which is not possible as $a,b \geq 1$. So we take $c \geq 3$. If $a=1$, then we have $$b^{c-2}+1=cb^{c-2} \geq 3b^{c-2} \Rightarrow 1 \geq 2b^{c-2} \geq 2b \Rightarrow b \leq \frac{1}{2} \rightarrow \text{Contradiction!}$$Similarly, there is no solution for $b=1$. So WLOG we can assume $a \geq b \geq 2$. But then $$c(ab)^{c-2}=a^{c-2}+b^{c-2} \leq 2a^{c-2} \Rightarrow 2 \geq cb^{c-2} \geq 3b \Rightarrow b \leq \frac{3}{2} \rightarrow \text{Contradiction!}$$ Thus, we arrive at a contradiction in all possible cases except for the given solution triplet. Hence, done. $\blacksquare$ EDIT: $1000^{\text{th}}$ post on AoPS
02.10.2020 06:56
It's funny how this problem can be solved by an amalgamation of advanced theorems like Zsigmondy's and Dirichlet's
22.10.2020 20:53
Very beautiful problem Let us devide the solution in 2 parts $Case1)$ $a=b=1$ we easily get that $n+c|2+n$ so we get that $c=2$. So one solution is $(a,b,c)=(1,1,2)$. $Case2)$at least one of the $a,b$ $\ne 1$. We use Zsigmondy's theorem and Dirichlet theorem for this part. Let us define a prime $p$ such that $p$ is a primitive divisor of $a^n+b^n$, we also get that $p \not | c$ and $p \not | n$.(From Zsigmondys theorem) Now applying Dirichlet's theorem we get that for a prime $q$ we get the following that $p|qn + c$, also $qn$ has no prime divisors less than $2014$, Now from the problem we know that $n+c|a^n+b^n+n$ $n+c|a^n+b^n-c$ also we get that $qn+c|a^{qn}+b^{qn}-c$ or $p|a^{qn}+b^{qn}-c$ but as we defined $p$ we know that $p|a^n+b^n$ which means that $p|a^{qn}+b^{qn}$ , combining these we get that $a^{qn}+b^{qn}-c=-c(mod p)$ , so it means that $p \not | a^{qn} + b^{qn} - c$. So the only solution is $(a,b,c)=(1,1,2)$
18.09.2021 21:08
v_Enhance wrote: Find all triples $(a,b,c)$ of positive integers such that if $n$ is not divisible by any prime less than $2014$, then $n+c$ divides $a^n+b^n+n$. Proposed by Evan Chen Choose \begin{align*} n \equiv -c \pmod p \\ n \equiv 1 \pmod {p-1} \end{align*}then $p|a^n+b^n+n \implies a^n+b^n \equiv c \pmod p \implies a^{p-2}+b^{p-2} \equiv a+b \equiv c \pmod p$ for all $p>2014$ implying $a+b=c$ Now choose \begin{align*} n \equiv -c \pmod p \\ n \equiv -1 \pmod {p-1} \end{align*}implying $a+b-abc=a+b-a(a+b) \implies (a-1)(a+b)=0$ or $(a,b,c)=(1,1,2)$ which works.
18.09.2021 22:53
The main idea is ISL 2005 N6. Let $S$ be the product of all primes less than $2014$. By Weak Dirichlet, there exist infinitely many primes $p$ which satisfy $$p\equiv 1\pmod{S}$$(This result can be proved by using cyclotomic polynomials). Such a prime $p$ with $p>\max(a,b)$ will be called good. For a good prime $p$, choose a positive integer $n$ with $$\begin{cases} n\equiv -c & \pmod{p} \\ n\equiv 1 & \pmod{p-1} \end{cases}$$ Hence $\gcd(n,p-1)=1$ so $\gcd(n,S)=1$. Therefore $$p\mid n+c\mid a^n+b^n+n\implies p\mid a+b-c$$ By choosing $p$ to be large enough we obtain $a+b=c$. Now choose a good prime $p$ and a positive integer $n$ with $$\begin{cases} n\equiv -c & \pmod{p} \\ n\equiv -1 & \pmod{p-1} \end{cases}$$ Such $n$ exists by CRT. Hence $\gcd(n,p-1)=1$ so $\gcd(n,S)=1$. Therefore \begin{align*} &p\mid n+c\mid a^n+b^n+n\\ &\implies p\mid\frac{1}{a}+\frac{1}{b}-c=\frac{a+b}{ab}-a-b\\ &\implies p\mid (ab-1)(a+b). \end{align*}By choosing $p$ to be large enough we obtain $(ab-1)(a+b)=0$. Hence $a=b=1$ so $\boxed{(a,b,c)=(1,1,2)}$. In this case $n+c=a^n+b^n+n$ so $(a,b,c)$ works.
27.10.2021 17:42
08.11.2021 13:48
Let $2 = p_1 < p_2 < \cdots < p_k$ be the primes below $2014$. Let $P = \prod p_i$. Pick a prime $p \equiv -1 \pmod P$ by dirichlet. Pick $n \equiv 2k+1 \pmod {p-1}$ and $n \equiv -c \pmod p$, by the chestnut ramification theorem. Note that $n$ is not divisible by any prime $< 2014$. Now we have $p | n+c | a^n + b^n + n \implies a^{2k+1} + b^{2k+1} - c \pmod p$. Since this is true for infinite primes, we have $a^{2k+1} + b^{2k+1} = c$. This means $(a,b,c) = (1,1,2)$, which clearly works, so we are done. $\blacksquare$
23.12.2021 13:51
Let $Q$ denote the product of odd primes till $2014$.Then generate primes $p \equiv -1 (mod Q)$ by dirichlet.Then choose $n$ satisfying, $n \equiv 1(mod Q)$,$n \equiv 1(mod p-1)$,$n \equiv -c(mod p)$.Such $n$ exists by CRT due to choice of $p$.However ,then by choosing $p$ very large,we get that $a+b=c$. Now,by modifying $n \equiv -1(mod p-1)$,then again by large choice of $p$,we get that $(ab-1)(a+b)=0$,giving $(a,b,c)=(1,1,2)$.
24.12.2021 18:11
Nothing new here.
13.02.2022 23:12
The key idea is to note: for any prime $p$, increasing $n$ by $p-1$ would change both $a^n + b^n + n, n + c$ by $-1$ modulo $p$. So after a appropriate number of increases we can force $p \mid n+c \mid a^n + b^n + n$. So $n + c \equiv a^n + b^n + n \pmod{p}$. Taking $p$ large we are done. Lastly, some technical details can be handled by Weak Dirichilet (or at least, the solution without Dirichilet is easily motivated by this analysis). $\blacksquare$
01.04.2022 15:17
The answer is $(a,b,c)=(1,1,2)$ only which clearly works. Let $P$ be the product of all the primes less than $2014$. By Dirichlet there exist infinitely many primes $p \equiv 1 \pmod{P}$. Henceforth when we say $p$ we refer to such a prime. By the Chinese Remainder Theorem, for every $p$ we can find some $n$ such that $n \equiv -c \pmod{p}$ and $n \equiv -q \pmod{p-1}$, where $q>2014$ is a prime. Then $n \equiv -q \pmod{P}$ so $n$ is not divisible by any primes less than $2014$, so we have $$p \mid n+c \mid a^n+b^n-c \implies a^{-q}+b^{-q} \equiv c \pmod{p}.$$Since there are infinitely many $p$ for which this is true, it follows that we must have $a^{-q}+b^{-q}=c$. If $c=1$, then we need $\min\{a,b\}=1$, otherwise $a^{-q}+b^{-q}\leq 2^{-q+1}<1$, but if $\min\{a,b\}=1$ then $a^{-q}+b^{-q}>1$, so $c \neq 1$. Then, $$a^{-q}+b^{-q} \leq 1^{-q}+1^{-q}=2,$$so we must have $a=b=1$, $c=2$, as desired. $\blacksquare$
21.01.2023 20:59
Take an arbitrarily large prime $p$ where $n=p-c$ satisfies the conditions. By Fermat's Little Theorem we reduce to \[\frac{1}{a^{c-1}}+\frac{1}{b^{c-1}}=c\]where the $\pmod p$ is removed. This clearly has only a single solution, $(a,b,c)=(1,1,2)$, which works. We are done. $\blacksquare$
09.06.2023 21:57
@above how do you know that $p-c$ is not divisible by any prime less than $2013$ if $p$ is large? In my opinion, that's like half the problem (also, you cannot always rely on $n = p-c$ because $c$ could be odd)
04.09.2023 21:05
got a hint on how to construct p Let $a=\prod_{\text{primes p}<2014}p$. By Dirichlet, there exist infinitely many primes p s.t. p=1 mod a. Let q>2014 be a prime. By CRT, for an arbitrary p we can find n s.t. n=-c mod p, n=(p-1)k-q so that n=-q mod a, meaning n satisfies the first property. Then, $p\mid n+c\mid a^n+b^n-c\implies a^{-q}+b^{-q}\equiv c\pmod p\rightarrow p\mid a^{-q}+b^{-q}-c$. For sufficiently large p s.t. LHS>RHS, we must have RHS=0, or $c=a^{-q}+b^{-q}\le 2$. $c=1\rightarrow a,b>1\rightarrow a^{-q}+b^{-q}\le1$. For equality to hold, we must have q=1,a=b=2, but q>2014, so no sol. $c=2\implies a=b=1$, which works, and is the only solution, as desired. $\blacksquare$
05.10.2023 11:11
The answer is $(a, b, c) = (1, 1, 2)$. Let $p$ be a large prime. Take a positive integer $n$ such that $n \equiv 1 (p-1)$ and $n \equiv -c (p)$. Then it's not hard to see that $\gcd(n, p(p-1)) = 1$. Thus by Dirichlet's theorem, there exists prime $q$ such that $q \equiv n (p(p-1))$. Thus $p \mid q + c \mid a^q + b^q + q$. By Fermat's little theorem, we have $a^q + b^q + q \equiv a + b + q \equiv a + b - c (p)$. Since $p$ is large enough, this forces $a + b = c$. Take a positive integer $m$ such that $m \equiv -1(p-1)$ and $m \equiv -c(p)$. Then similarly, there exists prime $r$ such that $r \equiv m (p)$. Thus $p \mid r + c \mid a^r+ b^r + r$ and Fermat's little theorem gives $a^r + b^r + r \equiv \frac{1}{a} + \frac{1}{b} -c$. Therefore $p \mid a + b - abc$, i.e $p \mid 1 - ab$. Hence $a = b = 1$, so $c = a + b = 2$. Thus $(a, b, c) = (1, 1, 2)$.$\blacksquare$
09.10.2023 07:05
Note that this is equivalent to $a^n + b^n \equiv c \pmod{n + c}$. Claim: $a^{c-1} + b^{c-1} = ca^{c-1}b^{c-1}$ Proof. Consider $n = p - c$ for sufficiently large primes $p$. By Dirichlet's take $p \not\equiv c \pmod{p_i}$ for $p_i \le 2013$. Then since \[ a^n + b^n \equiv c \pmod{p} \]it follows by FLT that \begin{align*} a^{1-c} + b^{1-c} &\equiv c \pmod{p} \\ b^{c-1} + a^{c-1} &\equiv ca^{c-1}b^{c-1} \pmod{p} \end{align*}Taking $p > \max\{b^{c-1} + a^{c-1}, ca^{c-1}b^{c-1}\}$ gives the result. $\blacksquare$ Claim: We must have that $c = 2$. Proof. If $c = 1$, the equation can not hold. If $c \ge 3$, then \[ ca^{c-1}b^{c-1} \ge a^{c-1}b^{c-1} + 2 > a^{c-1} + b^{c-1} \]giving contradiction. As such, $c = 2$. $\blacksquare$ The equation then becomes $a + b = 2ab$ which only holds if $ab = 1$, giving the solution $(a, b, c) = (1, 1, 2)$.
17.12.2023 01:01
Basically 2005 N6 but somewhat stronger. Note that the condition is equivalent to $$n+c \mid a^n + b^n - c.$$Now, let $p$ be any sufficiently large prime such that $p \equiv -1 \pmod {p_i}$ for every prime $p_i < 2013$, and $p \equiv -1 \pmod 4$ too. Then, notice that $\frac{p-1}2$ has no prime divisors less than $2013$. Now pick $n$ an odd multiple of $\frac{p-1}2$ and furthermore $n \equiv -c \pmod p$ using CRT. It follows that $$p \mid a^{(p-1)/2} + b^{(p-1)/2} - c.$$However, $a^{(p-1)/2}, b^{(p-1)/2} \in \{-1, 1\}$ and it follows that $p \mid \varepsilon - c$ for $\varepsilon \in \{-2, 0, 2\}$. By Pigeonhole, as there are infinitely many $p$, there exist infinitely many $p$ that divide the expression for some fixed $\varepsilon$. If $\varepsilon = -2$ or $0$, we have no positive integer solutions. Thus $\varepsilon = 2$ and $c=2$ uniquely. To finish, pick $n = p-2$ for some very large $p$. Then $$\frac 1a + \frac 1b \equiv a^{p-2} + b^{p-2} \equiv 2 \pmod p.$$In other words, this implies that $p \mid 2ab - a - b$, which implies $a+b=2ab$. The only solution to this is $(a, b) = (1, 1)$, which yields $(1, 1, 2)$ as the only triple.
12.03.2024 08:11
Our condition can be rewritten as $n+c \mid a^n+b^n-c$. We then use the following constructions: Vary a prime $p \equiv 1$ modulo every prime under 2013. There are infinitely many by Dirichlet. Set $n \equiv -c \pmod p \equiv -1 \pmod{p-1}$, which exists by CRT. This value of $n$ satisfies the problem statement, plus $p \mid n+c$. Thus we have \[0 \equiv a^n+b^n-c \equiv a^{-1} + b^{-1}-c \pmod p.\] As this holds for infinitely many $p$, the quantity must in fact equal 0, giving our only solution $\boxed{1,1,2}$.
09.05.2024 02:49
08.01.2025 22:28
Let $p>69420abc$ be a prime. Consider $n$ such that $n\equiv -c\pmod{p}$ and $n\equiv 1\pmod{2013!(p-1)}$. Then, by FLT, $a+b\equiv c\pmod{p}$. Consider $n$ such that $n\equiv -c\pmod{p}$ and $n\equiv -1\pmod{2013!(p-1)}$. Then, by FLT, $\frac1a+\frac1b\equiv c\pmod{p}$, so $a+b\equiv abc\pmod{p}$, so $ab\equiv 1\pmod{p}$. Since $a+b=c$ and $ab=1$, the only solution is $\boxed{(1,1,2)}$.