Consider two positive integers $a$ and $b$ such that $a^{n+1} + b^{n+1}$ is divisible by $a^n + b^n$ for infinitely many positive integers $n$. Is it necessarily true that $a = b$? (Boris Frenkin)
Problem
Source: Tournament of Towns, Senior O-Level , Spring 2019 p2
Tags: number theory, Sum of powers, Divisibility
11.05.2020 14:45
Suppose not, and WLOG take $a>b$. Note that $$a^n+b^n \mid a^{n+1}+b^{n+1} \Rightarrow a^n+b^n \mid a(a^n+b^n)-(a^{n+1}+b^{n+1}) \Rightarrow a^n+b^n \mid b^n(a-b)$$Then we get $$a^n+b^n \leq b^n(a-b) \Rightarrow \left(\frac{a}{b} \right)^n \leq a-b-1$$Taking $n$ sufficiently large gives the desired contradiction.
11.05.2020 14:49
Or absolutely murder it with Zsigmondy's theorem. Info link below: http://pommetatin.be/files/zsigmondy_en.pdf
12.05.2020 07:55
Yes a=b I proved that if gcd=d we have da1 and db1 gcd(a1,b1)=1 and I proved a1^n+b1^n divides d. b1^n.(a1-b1) if a1 not equal b1 we notice a1^n+b1^n divides d get a large n contradiction a1=b1
14.05.2020 10:26
Here is my proof with Zsigmondy as someone requested. Suppose $(a;b)=d$. Then let $ a=dx$ and $b=dy$, $(x;y)=1$. For infinitaly many n, $x^n+y^n/d(x^{n+1}+y^{n+1})$. Let $p$ be the primitive prime divisor of $x^n+y^n$. Then, $p/a^{n+1}+b^{n+1}$ for some p (this is true for infinitely many n, hence p will get big enough and pe greater than d, which is a constant). This is equivalent to $a^{n+1}\equiv-b^{n+1}(mod$ $p)$ for infinitely many n. $p/a^n+b^n$ $\Rightarrow$ $a^n\equiv-b^n(mod$ $p)$. So $a^{n+1}\equiv-b^na(mod$ $p)$. So $-b^{n+1}\equiv-b^n(mod$ $p)$ so $a\equiv b(mod$ $p)$. But $p$ does not divide $a-b$, hence contradiction. (This is true for every $(a;b)$ except for $(2;1)$, which is easy to analyze)
11.12.2020 23:18
20.12.2024 13:31
The answer is yes. Take $u=\gcd(a,b)$ and letĀ $ua'=a$ and $ub'=b$ where $\gcd(a',b')=1$. Then \[a^n+b^n\mid a^{n+1}+b^{n+1}\implies a^n + b^n \mid a^{n+1}-a^{n}b\implies a'^n + b'^n \mid a'^nu(a'-b')\implies a'^n + b'^n\mid u(a'-b') \]. where the last line follows from coprimality. If either of $a'$ or $b'$ is not $1$, then the divisor will grow arbitrarily large for large $n$ while the dividend is fixed, and hence $u(a'-b')$ must be zero, henceĀ $a'=b'\implies a=b$. If both $a'$ and $b'$ are $1$, then $a=b=u$.