Re: [PrimeNumbers] Re: Divisor problem.
- Jack Brennen wrote:
> Actually, the part in question (prove D < n^2) is by far the easierNow that I thought about it for five minutes, I realize that the
> "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).
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.