From: Peter-Lawrence.Montgomery@cwi.nl (Peter L. Montgomery)
Subject: Re: Powers in arithmetic progression.
Date: Mon, 31 Jul 2000 00:47:50 GMT
Newsgroups: sci.math.research
Summary: [missing]

In article <39844F0D.6057@club-internet.fr> pbornszt@club-internet.fr writes:
>Hi,
>
>the following problem has been proposed (but not used) for the 1997 IMO:
>"prove that if an infinite arithmetic progression of positive integers
>contains a perfect square and a perfect cube then it contains a perfect
>sixth power"
>
>My solution uses clearly that the given powers are 2 and 3. Does anybody
>knows if this result may be extend to powers n,m and n*m?
>
     You need GCD(m, n) = 1.  The sequence 9, 25, 41, 57, 73, ...
has squares but no fourth powers.


     Given the GCD(m, n) = 1 hypothesis, suppose the progression is
{a + b*j : j >= 0} where b >= 0.  We use induction on b.

Case 1:  b = 0.  Then the arithmetic progression is constant.
    Look at the exponents in the prime factors of a.

Case 2:  b = 1.  Then the progression includes all 
    sufficiently large integers.  Select a large (m*n)-th power.

Case 3:  b > 1.  Let p be a prime dividing b.  Suppose p^k || b 
    (meaning p^k divides b but p^(k+1) does not divide b).  
    
    Subcase 1:  p^k divides a.  By induction on b, there 
        exists x0 cuch that

             x0^(m*n) == a (mod b/p^k)

        Since GCD(p^k, b/p^k) = 1, the congruences

             x == x0 (mod b/p^k)
             x == 0  (mod p^k)

        have a common solution.  Any such x satisfies x^(m*n) == a (mod b).

    Subcase 2:  p^j || a where 0 < j < k. 
        j must be a multiple of m since a is an m-th power (mod b).
        j must be a multiple of n since a is an n-th power (mod b).
        Therefore j is divisible by m*n.  Find a solution to

            x^(m*n) == a/p^j  (mod b/p^j)

        and multiply it by p^(j/(m*n))

    Subcase 3:  GCD(p, a) = 1.  Then a is both an m-th power and 
        an n-th power in the multiplicative group of integers modulo p^k.
        By a well-known theorem on abelian groups, a must be
        an (m*n)-th power.  By this and induction, there exist x1 and x2
        such that
 
            x1^(m*n) == a (mod p^k)
            x2^(m*n) == a (mod b/p^k)

        By the Chinese Remainder Theorem, a is an (m*n)-th power.
-- 
E = m c^2.  Einstein = Man of the Century.  Why the squaring?

        Peter-Lawrence.Montgomery@cwi.nl    Home: San Rafael, California
        Microsoft Research and CWI