Author 
Topic: Arithmetic Progressions (9/13/2002) (Read 812 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Arithmetic Progressions (9/13/2002)
« on: Sep 16^{th}, 2002, 1:56pm » 
Quote Modify

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


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: Arithmetic Progressions (9/13/2002)
« Reply #1 on: Sep 17^{th}, 2002, 12:06am » 
Quote Modify

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^{k1}. 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^{u}q^{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, ..., p1, 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, ..., n1}. 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, ..., n1), 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 q1 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(q1). Also, notice that the equality gcd(n, q) = gcd(nq, 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(q1) = n  q <=> C = 1 + (n2)/(q1). This C is an integer if and only if q1 divides n2. Since gcd(n, n2) = 2, gcd(n, q1) = 2 as well, because it can't be 1, as we assumed that q was the second term in the AP. Suppose, then, that q1 = 2^{s}t, 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, q1) > 2, contrary to what has been deduced. Therefore t = 1 and q1 = 2^{s}. However, if it happened that s > 1, we could not have gcd(n, 2^{s}) = gcd(n2, 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.

« Last Edit: Sep 17^{th}, 2002, 6:32am by Pietro K.C. » 
IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



oliver
Newbie
Posts: 25


Re: Arithmetic Progressions (9/13/2002)
« Reply #2 on: Sep 17^{th}, 2002, 2:09am » 
Quote Modify

I'd go from the other way around and look at a general term for artihmetric progressions. P[n] = {i*d + a  d < (na)/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


IP Logged 



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: Arithmetic Progressions (9/13/2002)
« Reply #3 on: Sep 17^{th}, 2002, 6:35am » 
Quote Modify

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?


IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: Arithmetic Progressions (9/13/2002)
« Reply #4 on: Sep 17^{th}, 2002, 12:25pm » 
Quote Modify

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^{u}q^{v}...r^{w}, then phi(n) = p^{u1}q^{v1}...r^{w1}(p1)(q1)...(r1). If phi(n) = 1, we would necessarily have u1 = v1 = ... = w1 = 0 <=> u = v = ... = w = 1. Also, we must have p1 = q1 = ... = r1 = 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 u1 = 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.


IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



anonymous
Guest


Re: Arithmetic Progressions (9/13/2002)
« Reply #5 on: Feb 18^{th}, 2003, 12:15am » 
Quote Modify
Remove

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


IP Logged 



