Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Re: Divisor problem.

Expand Messages
  • Jack Brennen
    ... 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
    • 0 Attachment
      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.