Author |
Topic: Arithmetic Progressions (9/13/2002) (Read 826 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Re: Arithmetic Progressions (9/13/2002)
« Reply #1 on: Sep 17th, 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 pk with k > 1, the sequence goes from 1 to n but skips p, 2p, ..., pk-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 pk, hence the contradiction. Suppose then that p = 2 and n = 2k. 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 2k satisfies the condition.
I don't see how to generalize much from there... let's see. Pick any number n, and factor it into puqv...rw. 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 ac = 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 = 2st, 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 = 2s. However, if it happened that s > 1, we could not have gcd(n, 2s) = gcd(n-2, 2s) = 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 17th, 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 17th, 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 < (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
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Arithmetic Progressions (9/13/2002)
« Reply #3 on: Sep 17th, 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 17th, 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 = puqv...rw, then
phi(n) = pu-1qv-1...rw-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 = 2k;
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 18th, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
