$\textbf{N4:} $ Let $a,b$ be two positive integers such that for all positive integer $n>2020^{2020}$, there exists a positive integer $m$ coprime to $n$ with \begin{align*} \text{ $a^n+b^n \mid a^m+b^m$} \end{align*}Show that $a=b$ Proposed by ltf0501
Problem
Source: IMOC 2020
Tags: IMOC, number theory, Divisibility
Mr.C
08.09.2020 09:43
easy for $N4$ i guess. .
let $(a,b)=d$ so
$a=dx,b=dy$
we have
$ x^n + y^n| (x^m + y^m)d^{m-n}$ now for $x^n+y^n$ define $f(n)$ such that if $p$ is not a devisor of $d$ then $v_p(x^n+y^n)=v_p(f(n))$
else $v_p(f(n))=0$ so we have
$f(n)| d^{m-n}(x^m +y^m)$ so
$f(n)|x^m+y^m$ so we have
$f(n)|x^{(m,n)}+y^{(m,n)}=x+y$ so $f(n)$ is bounded above , and easy to check if $x>1$ or $y>1$ this can't happen , you can zigmondy for this part , the weak version of zigmondy also works ...
yayitsme
08.09.2020 10:28
Mr.C wrote: easy for $N4$ i guess. .
let $(a,b)=d$ so
$a=dx,b=dy$
we have
$ x^n + y^n| (x^m + y^m)d^{m-n}$ now for $x^n+y^n$ define $f(n)$ such that if $p$ is not a devisor of $d$ then $v_p(x^n+y^n)=v_p(f(n))$
else $v_p(f(n))=0$ so we have
$f(n)| d^{m-n}(x^m +y^m)$ so
$f(n)|x^m+y^m$ so we have
$f(n)|x^{(m,n)}+y^{(m,n)}=x+y$ so $f(n)$ is bounded above , and easy to check if $x>1$ or $y>1$ this can't happen , you can zigmondy for this part , the weak version of zigmondy also works ...
What is the weak version of zsigmondy?
Mr.C
08.09.2020 12:20
just using the fact that $x^n-y^n$ has a prime devisor that $x-y$ doesnt
Gaussian_cyber
08.09.2020 13:30
$d=gcd(a,b)$ Suppose both $a' , b' $ are not $1$
Then Consider an even $n$.
$a'^n + b'^n \mid d^{m-n} (a'^m + b'^m)$
$gcd(m,n) =1\implies m$ is odd. so $v_2(n) \neq v_2(m)$
So we should have $a'^n+b'^n \mid 2 . d^{m-n}$
So we got prime divisors of $a'^n+b'^n$ are finite.
Put $n=1$ mod product of $\phi$ of them and notice $v_2$ of it is either 0 or 1 . So Size Contradiction. $\blacksquare$
Prod55
27.11.2021 14:32
Define $f(n)=a^n+b^n,n>2020^{2020}$ Suppoce that $b-a\neq 0$. There exist $m$ with $(m,n)=1$ and $f(n)|f(m)$. If the set of prime divisors of $a^i+b^i,i=1,2,..$ is infinity take prime $p$ large enough such that $(p,a)=(p,b)=1$ and $p|a^n+b^n$ for some $n$. By bezout's lemma we can find $k,l\in \mathbb{Z}$ such that $nk+ml=1$. Note that $a^n=-b^n \pmod p, a^m=-b^m \pmod p\Rightarrow $ $a^{kn}=(-1)^kb^{kn} \pmod p, a^{ml}=(-1)^lb^{ml}\pmod p \Rightarrow p|a+b$ or $p|a-b$ contradiction etc (consider (a,b)=1 and $n=F(p_1-1)..(p_k-1),,F$ large integer, where $p_1..,p_k$ the set of prime divisors of $a^i+b^i,i=1,2,..$)