## Re: [PrimeNumbers] Re: Divisor problem.

Expand Messages
• ... Now that I thought about it for five minutes, I realize that the second half of the problem isn t so hard. First, if n is prime, D divides n^2. Simple.
Message 1 of 7 , Jul 29, 2002
Jack Brennen wrote:
> Actually, the part in question (prove D < n^2) is by far the easier
> "half" of the problem.
>
> Step 1. Prove that D/n^2 < 1/(1*2)+1/(2*3)+1/(3*4)+1(4*5)+...
> Term by term comparison should suffice here.
>
> Step 2. Prove that the infinite sum in step 1 converges to a
> value <= 1. One way is to prove by induction
> that the first m terms sum up to m/(m+1).

Now that I thought about it for five minutes, I realize that the
second "half" of the problem isn't so hard.

First, if n is prime, D divides n^2. Simple.

If n is composite, it has a smallest divisor, call it k.

We can easily see that D/n^2 > 1/k, so n^2/D < k.

If n^2/D is an integer > 1, it has a smallest prime divisor, call it m.

If n^2/D is divisible by m, then so is n.

But we already established that n has smallest divisor k, which
is necessarily greater than m. Contradiction.

Tidy that argument up for a few minutes, and you've got a perfect
score on an IMO problem.

Jack
Your message has been successfully submitted and would be delivered to recipients shortly.