Find all pairs $(a,b)$ of positive integers, such that for every $n$ positive integer, the equality $a^n+b^n=c_n^{n+1}$ is true, for some $c_n$ positive integer.
Problem
Source: Brazil EGMO TST 2022 #8
Tags: number theory
01.03.2022 16:58
If wlog $a\geq b$, assume we're in the case $a>b$, and consider all the $n>3$. By Zsigmondy's theorem, there exists a prime $p_n$ dividing $a^n+b^n$ , which doesn't divide the previous number. Since $p_n|c_n^{n+1}$, it follows that $p_n^{n+1}|c_n^{n+1}=a^n+b^n$. This implies $p_n<p_n^{1+1/n}\leq (c_n^{n+1})^{1/n}=\sqrt[n]{a^n+b^n}\leq \sqrt[n]{a^n\cdot 2^n}=2a$. However this implies that the sequence $p_n$ is bounded, in contradiction with the fact that the $p_n$ are primitive factors of $a^n+b^n$, meaning that there is an infinite quantity of distinct $p_n$s. So we may assume $a=b$, which gives $2a^n=c_n^{n+1}$. Since $a=1$ doesn't work, let $a=2^{e_0}p_1^{e_1}\cdots p_m^{e_m}$, with $2<p_1<...<p_m$ and $e_i>0$ (except $e_0\geq 0$). Taking $n+1>\max\{e_1,...,e_m\}$, this would imply $n+1|ne_i\implies n+1|e_i\implies n+1\leq e_i$ which is a contradiction. So we only have to look at $n_0$, which gives us $n+1|1+ne_0\implies n+1|n(e_0-1)\implies n+1|e_0-1$. Since this is true for all $n$, this implies $e_0=1$, i.e. $a=b=2$.
01.03.2022 17:00
Let $p$ be a prime such that $p|a+b$ then: Suppose that $p$ doesn't devise $a,b$ if we select $n$ such that $p$ doesn't devise $n$ we have: $U_p(a^n+b^n)=U_p(a+b)$ obviously a contradiction. So if $p|a+b$ then $p|a$,$p|b$. Let $U_p(a)=x$ and $U_p(b)=y$ with $x>y$ then$U_p(a^n+b^n)=y*n$ with is a contradiction.(because$n+1|yn$). So if $p|a+b$ then $p|a$,$p|b$ and $U_p(a)=U_p(b)$. Let $a=p^xa_1$ and $b=p^xb_1$ for some odd prime $p|a+b$ then: $p^{xn}(a_1^n+b_1^n)=c_n^{n+1}$ which means that: $n+1|xn+U_p(a_1^n+b_1^n)$ Let $k$ be the smallest number from which $p|a_1^k+b_1^k$(there's such a $k$ otherwise $n+1|nx$ from every $n$ a contradiction). Let $n=kl$ then $kl+1|klx+Up(a_1^k+b_1^k)+U_p(l)$. Now if we take $l$ such that $U_p(l)=0$ and $l$ go to infinity we have $x=U_p(a_1^k+b_1^k)$ Now if we take $l$ such that $U_p(l)=1$ and $l$ go to infinity we have $x=U_p(a_1^k+b_1^k)+1$ Contradiction. So $a+b=2^f$ and $U_2(a)=U_2(b)$ and there is no obb prime divesi $a,b$ which gives $a=b=2^{f-1}$ and now easy that $a=b=2$
04.03.2022 18:50
P2nisic wrote: Let $k$ be the smallest number from which $p|a_1^k+b_1^k$(there's such a $k$ otherwise $n+1|nx$ from every $n$ a contradiction). Let $n=kl$ then $kl+1|klx+Up(a_1^k+b_1^k)+U_p(l)$. Why $n=kl$?
05.03.2022 01:58
Here's a somewhat different solution. Notice that $(a, b) = (2, 2)$ works. We'll prove that it is the only solution. If $a=b$, $2a^n=c_{n}^{n+1}$. Let $p$ be an odd prime divisor of $a$. Then $n+1 \mid v_{p}(a)n \Leftrightarrow n+1 \mid v_{p}(a)$ which is fixed. Thus, $a=2^s$ and $n+1 \mid ns+1 \Leftrightarrow n+1 \mid s-1$ for any $n \Rightarrow s=1$. Now assume $a>b$. Let $(a, b)=d, a=xd, b=yd$ where $(x,y)=1$. By Zsigmondy there exists an odd prime $p$ that divides $x^k+y^k$ for an odd $k$. Taking $n=kp^e$ for some $e$, and looking at the exponent of $p$ on the condition, $p^ek+1 \mid p^ekv_{p}(d)+v_{p}(x^{kp^e}+y^{kp^e})$ which by LTE becomes $p^ek+1 \mid e-v_{p}(d)+v_{p}(x^k+y^k)$, a contradiction.
08.04.2022 00:52
Cant believe no one mentioned the similarity to 2011 A2: All such $c$ are less than $a+b$ for obvious reasons. That means there exists $X$ such that for infinitely many $n,$ $a^n+b^n=X^{n+1}.$ If either $a$ or $b$ are greater than $X$we have $(a/X)^n >x$ for $n$ sufficiently large. Same holds for $b$. Now, $X^{n+1}=a^n+b^n<=2X^n$ so $X$ is either $1$ or $2$. $X$ cannot be $1$ because $a^n+b^n>=2$. This gives $X=2$ and $a=b=2$ is the only possibility.
09.04.2022 00:16
It is even older than 2011 A2. It is from Russia 2005: https://artofproblemsolving.com/community/q2h32168p200066
15.05.2022 16:54
The answer is $a=b=2$. If $a=b$ we get the solution described above. WLOG $a>b$. Claim 1: $c_n$ is bounded Pf: $c_n^{n+1}=a^n+b^n<2a^n<a^{n+1}\implies c_n<a$ However notice that $$c_n^{2n+2}=(a^n+b^n)^2<2(a^{2n}+b^{2n})=2c_{2n}^{2n+1}\leq c_{2n}^{2n+2}$$so $c_n<c_{2n}$. This contradicts with claim 1. $\square$
13.08.2022 23:26
We claim that the only solution is the pair $(2,2)$ which clearly works. Now we show that this is the only pair that works. Claim: We cannot have an odd prime $p$ and an odd positive integer $n$ so that $a$ and $b$ are not divisible by $p$ and $p \mid a^n + b^n.$ proof Assume for contradiciton that the Claim is false. Then let $p$ and $n$ as above. Since $n$ is odd and $p$ does not divide $a$ and $b,$ we must have by LTE that for all odd positive integer $k:$ $$ v_p (a^{nk} + b^{nk}) = v_p(a^n+b^n) +v_p(k)$$On the other hand, by problems condition $$ nk+1 \mid v_p(a^{nk} + b^{nk})$$Conbining the two relation we get an absurd since we can make $nk+1$ arbitraly large while $v_p(a^n+b^n)+v_p(k)$ is nonzero and can be small (for instance, take $k$ sufficiently large with $p\nmid k$)$.\square$ Now we claim that if $a\ne b$ then there exist $p$ and $n$ as in the Claim; it will force $a=b.$ Lemma: If $a$ and $b$ are distinct positive integers, then exists an odd integer $n$ and an odd prime $p$ so that $p\nmid a,b$ and $p\mid a^n+b^n$ proof: First write $d=gcd(a,b)$ and then let $x={a}{/d}$ and $y={b}{/d}.$ Take $q$ a sufficiently large odd prime, more precisely, take $q$ so that $q>a+b$ and $q>r,$ for all $r\mid d.$ Then take $n=q$ and $p$ as an odd prime dividing $$ \frac{x^q + y^q}{x+y}$$For seeing that such $p$ exists, first note that, since $a\ne b$ by assumption, we cannot have $x=y=1$ and hence ${(x^q+y^q)}{/(x+y)}>1;$ now to show that $p$ is odd, note that since $gcd(x,y)=1,$ we must have that either $x,y$ are both odds or have different parities. In the later case, we would have that ${(x^q+y^q)}{/(x+y)}$ is odd and we are done; in the former case, just note that $$ \frac{x^q+y^q}{x+y} = x^{q-1}-x^{q-2}y+\dots-xy^{q-2}+y^{q-1}$$is odd since it is the sum of an odd number of odd numbers. So indeed $p$ exists and is odd. Now we have to show that $p$ satisfies the other condition, i.e., $p\nmid a,b.$ First note that since $x$ and $y$ are coprime we have $p\nmid x,y$ and so $p\mid a,b \iff p \mid d.$ Now note that since $q$ is odd, we have that $$ p\mid x^q+y^q \Rightarrow {(-xy^{-1})}^q \equiv 1 \pmod p$$where $y^{-1}$ denotes the multiplicative inverse of $y$ modulo $p.$ Then let $k$ denote the order of $-xy^{-1}$ modulo $p.$ By the above congruence, we have that $k \mid q$ and since $q$ is prime, it follows that $k=q$ or $k=1.$ If the former case happens, then we have that $p-1\ge k =q$ which implies that $p\nmid d$ by the choice of $q$(we have selected $q$ so that it is greater than all divisors of $d$) hence $p\nmid a,b$ and we are done. In the later case, we have that $p\mid x+y;$ hence by LTE we have $$ v_p\left(\frac{x^q+y^q}{x+y}\right)=v_p(q)$$since $p$ divides the above number by definition, we must have that $v_p(q)\ge 1,$ i.e. $p=q.$ Then $q \mid x+y\mid a+b$ which is an absurd since we have choosen $q>a+b.$ So the Lemma is proven. $\square.$ From the Claim and the Lemma, it follows that we must have $a=b$ and the condition becomes $2a^n$ is an $n+1$ power for all $n.$ We claim that $a$ must be $2.$ Indeed, let $l=v_2(a),$ then problems condition becomes $n+1 \mid 1 + nl$ for all positive integer $n.$ This is equivalen to $n+1 \mid l-1$ for all positive integer $n,$ which can only happen if $l-1 = 0$ (since $l$ is fixed an $n$ can be arbitraly large) i.e. $l=1.$ Now let $p$ be any odd prime, then the condition implies $n+1 \mid nv_p(a)$ for all positive integer $n;$ since $n+1$ and $n$ are coprime, this is equivalent to $n+1 \mid v_p(a)$ for all positive integer $n,$ which similarly implies $v_p(a)=0.$ Then we have that $v_2(a)=1$ and $v_p(a)=0,$ for all odd prime $p,$ i.e. $a=2.$ Clearly $(2,2)$ satisfies problems condition and so we are done.