## IMC 2010 Day 1 Problem 4

Let be two integers and suppose that is a positive integer such that the set is finite. Prove that .

*IMC 2010 Day 1 Problem 4*

**Solution:**

Suppose .

Step 1. .

Step 2. What if . (Fermat’s last theorem…)

Step 3. are square free. Suppose and take a prime divisor for . Take a very large prime such that . Then if it will follow that which is a contradiction.

Step 4. . For a large we have ( is still a prime factor of ). Notice that and so on until you find integers such that and from here . This leads us to the next step. (the idea is and simplify; here we use and is squarefree)

Step 5. If then working modulo we see that there are at most residues, which means the set is infinite contradiction.

Advertisements

Categories: Algebra, IMO, Number theory, Olympiad, Problem Solving
diophantine equations, IMC, number theory

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)?

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

For step 3: if is not square free, and the set we talk about is finite, then for a prime factor of with power greater than one we have that so, since we have so finally (while we can choose to contradict this).

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

If you have other questions, please ask. Thanks for reading my blog. 🙂

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 😀

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 is square free. Pick big enough such that is representable. Then because divides and the RHS it must divide . is coprime with so must divide . Since is prime, and is squarefree we must have that divides . And like this we can divide both with and continue the same reasoning until we have in the RHS. Here we reason one more time to get which is a contradiction.

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!

I’m glad it is clear now.