Home > Algebra, IMO, Number theory, Olympiad, Problem Solving > IMC 2010 Day 1 Problem 4

## IMC 2010 Day 1 Problem 4

Let $a,b$ be two integers and suppose that $n$ is a positive integer such that the set $\Bbb{Z}\setminus \{ax^n+by^n | x,y \in \Bbb{Z}\}$ is finite. Prove that $n=1$.
IMC 2010 Day 1 Problem 4

Solution:
Suppose $n>1$.
Step 1. $\gcd(a,b)=1$.
Step 2. What if $\pm a=b=1$. (Fermat’s last theorem…)
Step 3. $a,b$ are square free. Suppose $a \geq 2$ and take $p$ a prime divisor for $a$. Take $r$ a very large prime such that $ax^n+by^n=pr$. Then if $p^2 |a$ it will follow that $p|r$ which is a contradiction.
Step 4. $n > 2$. For a large $k$ we have $ax^n+by^n=p^{nk+2}$ ($p$ is still a prime factor of $a$). Notice that $p|x,y$ and so on until you find $z,t$ integers such that $az^n+bt^n=p^2$ and from here $p^n |p^2$. This leads us to the next step. (the idea is $p|a \Rightarrow p|y \Rightarrow p|x$ and simplify; here we use $\gcd(a,b)=1$ and $a$ is squarefree)
Step 5. If $n=2$ then working modulo $8$ we see that there are at most $6$ residues, which means the set is infinite contradiction.

1. November 24, 2013 at 10:48 am

Hi, could you explain me a couple of passages which aren’t clear to me?
The first is how to face step 2. Where do you use the fact that a,b are square-free? Why p must divide x,y with your assumptions (I guess this is something related to the fact that a,b are square-free)?

• November 24, 2013 at 12:33 pm

For step 2 if $n>2$ we can use Fermat’s last theorem (quite a sledgehammer) to see that all the numbers of the form $k^n$ or $-k^n$ are not attainable (the sign depends on $a,b$). If $n=2$ look at the numbers which give residue $2$ modulo $4$.

For step 3: if $a$ is not square free, and the set we talk about is finite, then for $p$ a prime factor of $a$ with power greater than one we have that $ax^n+by^n=pr$ so, since $\gcd(a,b)=1$ we have $p|y$ so finally $p|r$ (while we can choose $r$ to contradict this).

Step 4 is in fact $n>2$ (typo error…) and it is described how to reach a contradiction.

2. November 24, 2013 at 12:52 pm

For step 2: are we allowed to use Fermat in the competition?
Step 3 was clear to me, the passage that I still don’t understand is why (in step 4) p must divide both x and y (why it can’t be that the sum is 0 (modulo $p^{nk+2}$) but both $ax^n$ and $by^n$ Are not 0?).
Thank you for your patience, this is an interesting blog 😀

• November 24, 2013 at 2:58 pm

Of course we can use Fermat’s theorem. It is a well known mathematical fact. There were cases in other years where a problem was a particular case of a general theorem. The ones who applied that theorem were given full scores.

For step 4 I still don’t understand where is the problem. You know that $a$ is square free. Pick $k$ big enough such that $p^{kn+2}$ is representable. Then because $p$ divides $a$ and the RHS it must divide $yb^n$. $b$ is coprime with $a$ so $p$ must divide $y$. Since $p$ is prime, and $a$ is squarefree we must have that $p$ divides $x$. And like this we can divide both $x,y$ with $p$ and continue the same reasoning until we have $p^2$ in the RHS. Here we reason one more time to get $p^n | p^2$ which is a contradiction.

3. November 24, 2013 at 3:12 pm

Now it is clear, p is a prime which divides a and not a generic prime. Excuse me, it was obvious, I just missed the assumption that p divides a 😦 thank you very much!

• November 24, 2013 at 3:16 pm

I’m glad it is clear now.