(a,0) alwyas works where a is a positive integer.

The problem says "positive integers".

zhaobin wrote: Let $m,n$ be positive integer numbers,Prove that there exist infinite many couples of positive integer nubmers $(a,b)$ such that \[a+b| am^a+bn^b.\] Let $p$ a prime number which does not divide $mn$ Choose $(a,b)=(k(p-1)^2,k(p-1))$ for any positive integer $k$ : $m^{k(p-1)^2}\equiv n^{k(p-1)}\equiv 1\pmod p$ $\implies$ $p|(m^{k(p-1)^2}-n^{k(p-1)})$ $\implies$ $kp(p-1)|k(p-1)^2(m^{k(p-1)^2}-n^{k(p-1)})$ $\implies$ $a+b|a(m^a-n^b)$ $\implies$ $a+b|(a+b)n^b+a(m^a-n^b)$ $\implies$ $a+b|am^a+bn^b$ Q.E.D.

zhaobin wrote: Let $m,n$ be positive integer numbers,Prove that there exist infinite many couples of positive integer nubmers $(a,b)$ such that \[a+b| am^a+bn^b.\] The problem says "co-prime positive integers (a,b)". [moderator edit: thanks, edited. ]

lin wrote: The problem says "co-prime positive integers (a,b)". I dont see where it says such a thing :

pco wrote: lin wrote: The problem says "co-prime positive integers (a,b)". I dont see where it says such a thing : Zhaobin loss it.In Chainese:互素的正整数a,b

Thanks,Mr Lin.I am sorry for my careless.

If $a+b=p$ is prime, then $(a,b)=gcd(a,b)=1$. When $(a,b)=1$ your condition equavalent to $a+b|n^b-m^a$. If $p\not |mn$, and $a+b=p$ then $p|n^bm^b-m$. If $n=g^x\mod p, m=g^y\mod p$, then $(x+y)b=y\mod p-1$. We can solve it (find b) if $ord_p(m)|ord_p(mn)$. It is true for prime divisors $p|(mn)^b-m$, suth that $(p,mn)=1$. Algoritm: for any $b$ we find $p>b$, suth that $p|(mn)^b-m, p\not |mn$ and take $a=p-b$.

Rust wrote: Algoritm: for any $b$ we find $p>b$, suth that $p|(mn)^b-m, p\not |mn$ and take $a=p-b$. It remains to prove that you can find such $p$ for infinitely many $b$. The condition $p>b$ main lead to impossibility. I have an equivalent possible solution but I need to prove that there exists infinitely many prime $p$ such that $ord_p(mn)=p-1$ and I dont succeed proving this.

pco wrote: Rust wrote: Algoritm: for any $b$ we find $p>b$, suth that $p|(mn)^b-m, p\not |mn$ and take $a=p-b$. It remains to prove that you can find such $p$ for infinitely many $b$. The condition $p>b$ main lead to impossibility. I have an equivalent possible solution but I need to prove that there exists infinitely many prime $p$ such that $ord_p(mn)=p-1$ and I dont succeed proving this. I can prove, that exist prime $p|m^{b-1}n^b-1$ and $p>b$. But it is long. We can found one solution $(a_0,b_0)$ suth that $a_0+b_0=p$ and take $a_k=a_0p^k,b_k=b_9p^k$. It is easy to show, that $p|m^{a_0}-n^{b_0}\to p^{k+1}|m^{a_k}-n^{b_k}.$ If $m,n$ are odd we take $(a_0,b_0)=(1,1),p=2$. Else take $b_0=2, a_0=p-2$ and p is any prime divisor of $mn^2-1$. Because p is odd $p>2$.

Rust wrote: Else take $b_0=2, a_0=p-2$ and p is any prime divisor of $mn^2-1$. Because p is odd $p>2$. But there is only a finite number of such $p$ divisor of $(mn)^2-1$

pco wrote: Rust wrote: Else take $b_0=2, a_0=p-2$ and p is any prime divisor of $mn^2-1$. Because p is odd $p>2$. But there is only a finite number of such $p$ divisor of $(mn)^2-1$ But infinetely pairs $(a_k,b_k)=(a_0p^k,b_0p^k)$. When $m,n$ are odd I found infinetely many $(a_k,b_k)$, suth that $(a_k+b_k)^2|a_km^{a_k}+b_kn^{b_k}$. If exist (b,p), suth that $p^2|n^{b_0}m^{b_0-1}-1$, and $p>b_0$ then it is true for all $m,n$.

Rust wrote: But infinetely pairs $(a_k,b_k)=(a_0p^k,b_0p^k)$. When $m,n$ are odd I found infinetely many $(a_k,b_k)$, suth that $(a_k+b_k)^2|a_km^{a_k}+b_kn^{b_k}$. If exist (b,p), suth that $p^2|n^{b_0}m^{b_0-1}-1$, and $p>b_0$ then it is true for all $m,n$. I'm sorry to insist but then it seems to me that you no longer respect the added constraint $\gcd(a,b)=1$

oh, I forget about $(a,b)=1$. But we can found $(a_k,b_k)=1$ too. Early we found $(a_0,b_0,p>b_0)$. Let we have $(a_{k-1}=p^k-b_{k-1},b_{k-1}<p^k)$, suth that $p^k|a_{k-1}m^{a_{k-1}}+b_{k-1}n^{b_{k-1}}$ or $p^k|(mn)^{b_{k-1}}-m^{p^k}$. We need $b_k=b_{k-1}+r(p^k-p^{k-1}),r<p$, suth that $p^{k+1}|(mn)^{b_k}-m^{p^{k+1}}$. Obviosly $p^{k+1}|m^{p^{k+1}}-m^{p^k}$. Let $m^{p^k}=m_0+m_1p+...+m_{k-1}p^{k-1}+m_kp^k+...$ and $(mn)^{b_{k-1}}=m_0+m_1p+...+m_{k-1}p^{k-1}+cp^k+....$. Obviosly work $r=\frac{m_k-c}{d}\mod p$, were $d$ satisfyed $(mn)^{p-1}-1=dp^l\mod p^{l+1}$. When $l>1$ we found $(a_k=p^k-b_k,b_k)$, suth that $p^{k+l}|n^{b_k}-m^{a_k}$.

If $m=n=1$ then any pair $(a,b)$ works, so assume $m\neq 1$. Let $a=k$ and $b=p-k$ for some prime $p\not | mn$. The problem reduces to finding $k$ such that $p | m^k-n^{p-k}$ or similarly $m^k \equiv n^{p-k} \Longleftrightarrow (mn)^k \equiv n \mod p$ equivalently $p | (mn)^k -n$ for some $k<p$ We wish to find infinitely many pairs $(k,p)$. Let $S= \{(mn)^k-n \, | k \in \mathbb{N}\}$ which is unbounded since $m>1$, and suppose for the sake of contradiction that only finitely many primes divided the numbers in $S$. Say those primes are $p_1,p_2,...,p_N$, then all numbers in $S$, call them $s(k)=(nm)^k-n$, are of the form $s(k)=p_1^{\alpha_1}\dots p_N^{\alpha_N}$. As $k$ gets arbitrarily large some primes will have arbitrarily high orders dividing $s(k)$. For any $M\in \mathbb{N}$ we pick $k_0$ large enough so that $s(k)$ will have some prime dividing it with order $\ge M$ for all $k \ge k_0$. Then among the numbers $s(k_0), s(k_0+1),...,s(k_0+N)$, there will be two numbers $i<j$ such that $s(k_0+i)$ and $s(k_0+j)$ that have the same prime $p_{\ell}$ with order $\ge M$ dividing both of them. Hence $p_{\ell}^M$ divides $s(k_0+i)-s(k_0+j) = (mn)^{k_0+i}[(mn)^{i-j}-1]$ Since $p_{\ell}$ divides $(mn)^{k_0+i}-n$, the order of $p_{\ell}$ dividing $(mn)^{k_0+i}$ is bounded by the order of $p_{\ell}$ dividing $n$, so there is still some arbitrarily high order of $p_{\ell}$ dividing $(mn)^{i-j}-1$, but this value is also bounded since $|i-j| \le N$, a contradiction. So we can find infinitely many primes dividing $S$. If there is a pair $(k,p)$ such that $k\ge p$ then since Fermat's Little Theorem gives $(mn)^{p-1} \equiv 1 \mod p$ we can write $k=q(p-1) + k'$ with $k' < p-1$ and $(mn)^{k'} \equiv n \mod p$, so we have a new pair $(k',p)$ with the desired property. This completes the proof

ocha wrote: This is too simple, it must be wrong somewhere.. If $m=n=1$ then any pair $(a,b)$ works, so assume $m\neq 1$. Let $a=k$ and $b=p-k$ for some prime $p$, such that neither $m$ nor $mn \equiv 0,1 \mod p$. The problem reduces to finding $k$ such that $p | m^k-n^{p-k}$ or equivalently $m^k \equiv n^{p-k} \mod p$ Since $(m,p)=(n,p)=1$, multiplicative inverses are well defined mod p so we need $m^kn^{k} \equiv n^{p}\equiv n \mod p$. Now since $m$ and $mn \not \equiv 1\mod p$ we can find $0<k_0< p$ such that $(mn)^{k_0} \equiv n \mod p$, because $mn$ creates a full residue class mod p. Since, all primes $p > mn$ satisfy the required condition we can find infinitely many pairs $(p,k_0)$ and the conclusion follows. mn must be a primitive root of p.

ZHANGWENZHONGKK wrote: mn must be a primitive root of p. rookie mistake. I think i've fixed the proof though.

If you knew this problem which happens to be from the very same nation, the problem is really easy once you make a couple of obvious transformations.

ocha wrote: If $m=n=1$ then any pair $(a,b)$ works, so assume $m\neq 1$. Let $a=k$ and $b=p-k$ for some prime $p\not | mn$. The problem reduces to finding $k$ such that $p | m^k-n^{p-k}$ or similarly $m^k \equiv n^{p-k} \Longleftrightarrow (mn)^k \equiv n \mod p$ equivalently $p | (mn)^k -n$ for some $k<p$ We wish to find infinitely many pairs $(k,p)$. Let $S= \{(mn)^k-n \, | k \in \mathbb{N}\}$ which is unbounded since $m>1$, and suppose for the sake of contradiction that only finitely many primes divided the numbers in $S$. Say those primes are $p_1,p_2,...,p_N$, then all numbers in $S$, call them $s(k)=(nm)^k-n$, are of the form $s(k)=p_1^{\alpha_1}\dots p_N^{\alpha_N}$. As $k$ gets arbitrarily large some primes will have arbitrarily high orders dividing $s(k)$. For any $M\in \mathbb{N}$ we pick $k_0$ large enough so that $s(k)$ will have some prime dividing it with order $\ge M$ for all $k \ge k_0$. Then among the numbers $s(k_0), s(k_0+1),...,s(k_0+N)$, there will be two numbers $i<j$ such that $s(k_0+i)$ and $s(k_0+j)$ that have the same prime $p_{\ell}$ with order $\ge M$ dividing both of them. Hence $p_{\ell}^M$ divides $s(k_0+i)-s(k_0+j) = (mn)^{k_0+i}[(mn)^{i-j}-1]$ Since $p_{\ell}$ divides $(mn)^{k_0+i}-n$, the order of $p_{\ell}$ dividing $(mn)^{k_0+i}$ is bounded by the order of $p_{\ell}$ dividing $n$, so there is still some arbitrarily high order of $p_{\ell}$ dividing $(mn)^{i-j}-1$, but this value is also bounded since $|i-j| \le N$, a contradiction. So we can find infinitely many primes dividing $S$. If there is a pair $(k,p)$ such that $k\ge p$ then since Fermat's Little Theorem gives $(mn)^{p-1} \equiv 1 \mod p$ we can write $k=q(p-1) + k'$ with $k' < p-1$ and $(mn)^{k'} \equiv n \mod p$, so we have a new pair $(k',p)$ with the desired property. This completes the proof

ocha wrote: If $m=n=1$ then any pair $(a,b)$ works, so assume $m\neq 1$. Let $a=k$ and $b=p-k$ for some prime $p\not | mn$. The problem reduces to finding $k$ such that $p | m^k-n^{p-k}$ or similarly $m^k \equiv n^{p-k} \Longleftrightarrow (mn)^k \equiv n \mod p$ equivalently $p | (mn)^k -n$ for some $k<p$ We wish to find infinitely many pairs $(k,p)$. Let $S= \{(mn)^k-n \, | k \in \mathbb{N}\}$ which is unbounded since $m>1$, and suppose for the sake of contradiction that only finitely many primes divided the numbers in $S$. Say those primes are $p_1,p_2,...,p_N$, then all numbers in $S$, call them $s(k)=(nm)^k-n$, are of the form $s(k)=p_1^{\alpha_1}\dots p_N^{\alpha_N}$. As $k$ gets arbitrarily large some primes will have arbitrarily high orders dividing $s(k)$. For any $M\in \mathbb{N}$ we pick $k_0$ large enough so that $s(k)$ will have some prime dividing it with order $\ge M$ for all $k \ge k_0$. Then among the numbers $s(k_0), s(k_0+1),...,s(k_0+N)$, there will be two numbers $i<j$ such that $s(k_0+i)$ and $s(k_0+j)$ that have the same prime $p_{\ell}$ with order $\ge M$ dividing both of them. Hence $p_{\ell}^M$ divides $s(k_0+i)-s(k_0+j) = (mn)^{k_0+i}[(mn)^{i-j}-1]$ Since $p_{\ell}$ divides $(mn)^{k_0+i}-n$, the order of $p_{\ell}$ dividing $(mn)^{k_0+i}$ is bounded by the order of $p_{\ell}$ dividing $n$, so there is still some arbitrarily high order of $p_{\ell}$ dividing $(mn)^{i-j}-1$, but this value is also bounded since $|i-j| \le N$, a contradiction. So we can find infinitely many primes dividing $S$. If there is a pair $(k,p)$ such that $k\ge p$ then since Fermat's Little Theorem gives $(mn)^{p-1} \equiv 1 \mod p$ we can write $k=q(p-1) + k'$ with $k' < p-1$ and $(mn)^{k'} \equiv n \mod p$, so we have a new pair $(k',p)$ with the desired property. This completes the proof

I'm very sorry for the flood, but where can I found results of the olympiad?

Any pair of coprime positive integers $(a,b)$ with $a+b|(mn)^a-n^{a+b}$ and $(a+b,n)=1$ is an answer to the original equation. Now let $a+b=p$ where $p$ is a prime number. So it suffices to find infinitely many prime numbers coprime to $n$ like $p$ such that for some $1\le a \le p-1$, $(mn)^a \equiv n (\mod p)$ which is a result of the Kobayashi Theorem.

nice solution when m,n are of same parity It is clear that the condition is equivalent to $a+b|m^a-n^b$ Case 1 Let $m-n$ is not a power of $2$. There exists an odd prime $p$ such that $p|m-n$.Choose $a=b=p^k$ where $k \ge 1$.

Proof

Case 2 Let $m-n$ be a power of $2$,i.e,$m-n=2^k$ more some $k \ge 1$ Choose $a=b=2^r$ where $r \ge 1$.

Proof

sayantanchakraborty wrote: nice solution when m,n are of same parity It is clear that the condition is equivalent to $a+b|m^a-n^b$ Case 1 Let $m-n$ is not a power of $2$. There exists an odd prime $p$ such that $p|m-n$.Choose $a=b=p^k$ where $k \ge 1$.

Proof

Case 2 Let $m-n$ be a power of $2$,i.e,$m-n=2^k$ more some $k \ge 1$ Choose $a=b=2^r$ where $r \ge 1$.

Proof

your solution is false because $gcd(a,b)=1$

zhaobin wrote: Let $m,n$ be positive integer numbers. Prove that there exist infinite many couples of positive integer nubmers $(a,b)$ such that \[a+b| am^a+bn^b , \quad\gcd(a,b)=1.\] Note that $am^a+bn^b\equiv b(n^b-m^a) \pmod{a+b}$. So, it's enough to find $a,b$ that $a+b\mid (mn)^a-n^{a+b}$ and $\gcd (a,b) =\gcd (n,a+b)=1$. We can easily exclude the case when $mn=1$. We'll show that there exist infinitely many such $(a,b)$ with an extra condition that $a+b=p>n$ is a prime number. Note that $a+b$ being prime number immediately gives us $\gcd (a,b)=1$ and $\gcd (n,a+b)=1$. By Kobayashi's, there exist infinitely many primes $p>n$ that divide a number in the sequence $\{ (mn)^a-n\}_{a\in \mathbb{Z}^+}$. For each such prime we have $p\mid (mn)^a-n\implies p\mid (mn)^a-n^p=(mn)^a-n^{a+b}$. (By FLT, we can reduce $a$ in modulo $p-1$ so that $0< a<p$.)