wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Arithmetic Progressions (9/13/2002)
        
(Message started by: william wu on Sep 16^th, 2002, 1:56pm)

Title: Arithmetic Progressions (9/13/2002)
Post by william wu on Sep 16^th, 2002, 1:56pm

For which integers n>1 does the set of positive integers less than and relatively prime to n constitute an arithmetic progression?

Title: Re: Arithmetic Progressions (9/13/2002)
Post by Pietro K.C. on Sep 17^th, 2002, 12:06am

Well, for all prime numbers p, the sequence of numbers satisfying the condition is clearly an AP with common difference equal to 1.

For n the power of a prime, say p^k with k > 1, the sequence goes from 1 to n but skips p, 2p, ..., p^k-1. If p is not 2, then this cannot be an AP, otherwise the first two terms would be (1,2) and the common difference would have to be 1, which would make the next terms be (3, ..., p - 1, p). But p is not prime with p^k, hence the contradiction. Suppose then that p = 2 and n = 2^k. The first two terms are now (1, 3), which makes the next terms necessarily be 5, 7, 9, etc. This is indeed an AP, so we conclude that, in addition to the primes, any number of the form 2^k satisfies the condition.

I don't see how to generalize much from there... let's see. Pick any number n, and factor it into p^uq^v...r^w. Suppose that p is its smallest prime factor, and that it is not 2. Therefore, the first two terms in the sequence of numbers prime with n would have to be (1,2), and hence the common difference would have to be 1. Continuing the sequence, we would have to have (1, ..., p-1, p). But p is NOT included in that sequence! Therefore, if any number n is to satisfy the condition of this problem, it must have 2 as its smallest prime factor.

Suppose then that n does have a factor of 2. Then it is not prime with any even number, hence the terms of an eventual AP must be included in the set {1, 3, ..., n-1}. Let p be the next smallest factor of n. If it is different from 3, then the AP would actually have to be (1, 3, ..., n-1), using the same logic as before - but since this includes all odd numbers from 1 to n, it will include p, which is a contradiction. So the next smallest factor HAS to be 3. I think this can be continued to some contradiction; my feeling is that the only numbers satisfying the problem statement are primes and powers of 2.

Maybe if we try a different approach... say q is the smallest prime that does not appear in the factorization of n (we proved it cannot be 2). Suppose also that n > 2q. Then the first two terms of the AP must be (1, q); because any number from 2 to q-1 is either a prime smaller than q or has a factorization in terms of such primes. That means the AP, if it exists, must be of the form a_c = 1 + c(q-1). Also, notice that the equality gcd(n, q) = gcd(n-q, q) = 1 implies that the last term in the AP must be n - q; and hence that there exists a positive integer C such that 1 + C(q-1) = n - q <=> C = -1 + (n-2)/(q-1). This C is an integer if and only if q-1 divides n-2. Since gcd(n, n-2) = 2, gcd(n, q-1) = 2 as well, because it can't be 1, as we assumed that q was the second term in the AP. Suppose, then, that q-1 = 2^st, where t is some odd number. Since t < q, it must have some prime factor which is also a factor of n, by the construction of q. This would mean gcd(n, q-1) > 2, contrary to what has been deduced. Therefore t = 1 and q-1 = 2^s. However, if it happened that s > 1, we could not have gcd(n, 2^s) = gcd(n-2, 2^s) = 2; at least one of them would have to be 4, given that n is even. It must be that q - 1 = 2 <=> q = 3. But we had showed up there that, if n was not a power of 2, its next factor must be 3. Huh. I didn't think I'd use the result above. Imagine that.

So there are two more cases left: 1 < n < q and q < n < 2q, with n not prime and not a power of 2. In the first, the AP would just be (1); in the second, just (1, q). I'm not too sure how to treat these right now. I'll post more later.

Title: Re: Arithmetic Progressions (9/13/2002)
Post by oliver on Sep 17^th, 2002, 2:09am

I'd go from the other way around and look at a general term for artihmetric progressions.

P[n] = {i*d + a | d < (n-a)/i, d integer}

Hmm, William, does your definition of arithmethric progressions allow a != 0, i.e. is 11,13,15,... also an arithmetric progression?

oliver

Title: Re: Arithmetic Progressions (9/13/2002)
Post by Pietro K.C. on Sep 17^th, 2002, 6:35am

Oops. There was a mistake in my previous post, which I've just corrected, but which renders the proof incomplete. I thought I had it, but then noticed that the numbers prime to 6 are (1, 5), and anything with only two terms is an AP. Sorry. Any ideas on how to complete it?

Title: Re: Arithmetic Progressions (9/13/2002)
Post by Pietro K.C. on Sep 17^th, 2002, 12:25pm

Eureka! I've done it! It's really quite simple, I guess I didn't see it before because it was 4am. Here it is.

Let phi(n) be the Euler phi function evaluated at n, and take the first case, where 1 is the only number less than n and prime with it. Then we would have phi(n) = 1. However, it is well known that, if n = p^uq^v...r^w, then

phi(n) = p^u-1q^v-1...r^w-1(p-1)(q-1)...(r-1).

If phi(n) = 1, we would necessarily have u-1 = v-1 = ... = w-1 = 0 <=> u = v = ... = w = 1. Also, we must have p-1 = q-1 = ... = r-1 = 1 <=> p = q = r = 2. Hence, the only number satisfying phi(n) = 1 is 2, which we have already included in the partial proof before.

Now consider the second case, where n had only 1 and q less than and prime with it. This implies phi(n) = 2. Since 2 is a prime, one of the factors of phi(n) in the above given formula must be divisible by (and hence equal to) 2, the others being 1. And because we are supposing p, q, ..., r to be distinct primes, it is clear that the largest among them cannot be greater than 3. Otherwise a factor of at least 3 would appear in phi(n), which is contrary to our assumption that phi(n) = 2.

We know also from the first post that n is even, therefore p = 2. If u > 1, u - 1 > 0, and all the other factors must be equal to unity. Also, because for phi(n) = 2, it is necessary that u-1 = 1 <=> u = 2 and n = 4, which was already included in our previous solution. However, if p = 2 and u = 1, we must have q = 3 and v = 0, evidently. This gives us n = 6, which we had overlooked before.

This concludes the proof, because n can have no larger factors than 3 and still satisfy phi(n) = 2. So the only numbers that meet the requirement of the problem are:

n prime;
n = 2^k;
n = 6.

Title: Re: Arithmetic Progressions (9/13/2002)
Post by anonymous on Feb 18^th, 2003, 12:15am

This is IMO 1991 problem 2. There are two different approaches to solve this problem.

1) mod 3
2) gcd(a,a+2)=gcd(a,a+4)=1 for all odd integers a