Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Euclid's formula

  1. Jan 30, 2010 #1
    1. The problem statement, all variables and given/known data

    Proof and show that in Euclid's formula for perfect numbers, n must be prime.

    2. Relevant equations


    3. The attempt at a solution

    I can show it by plugging in the number but I cannot prove it...any ideas?
  2. jcsd
  3. Jan 30, 2010 #2
    Try showing that if 2n-1 is prime, then n is prime. You can do this by assuming it is composite (n=ab), and finding a divisor of 2n-1 (namely 2a-1)
  4. Jan 30, 2010 #3
    Sounds like you are in History of Mathematics...I'm trying to figure this problem out (among many others)..to bad the hint in the back of the book says the same thing as what was posted previously..and that doesn't help
  5. Jan 31, 2010 #4
    I am not sure whether the problem you have is to show that n does not divide 2^n-1 ( that is they are relatively prime) or to show that if 2^n-1 is prime than n is prime ( in which case i am not sure that the latter even holds). However, if it is the former here is another approach to this problem: Suppose the contrary: that is let [tex] 2^n-1[/tex] be a prime number and n a number not relatively prime to it. Now, let [tex] p_1[/tex] be a prime divisor of n, and let k be the smallest positive integer for which [tex]p_1[/tex] divides [tex]2^k-1[/tex]. Now from Fermat's little theorem we would get that [tex]p_1[/tex] is also a factor of [tex]2^{p_1-1}-1[/tex]. Hence [tex]k\leq p_1-1<p_1.[/tex]

    Now your task is to prove that q divides n. Assume the contrary, by expressing n=hq+r.
    I will stop here before i get in trouble from PF Moderators!

    Hope this was helpful.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook