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.

Advertisements
  1. Peter
    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.

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

  2. Peter
    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. Peter
    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.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: