Proof of Euclid's Formula: n Must Be Prime

[imprank6]

Homework Statement

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

Homework Equations

(2^(n-1))((2^n)-1))

The Attempt at a Solution

I can show it by plugging in the number but I cannot prove it...any ideas?

 

[VeeEight]

Try showing that if 2ⁿ-1 is prime, then n is prime. You can do this by assuming it is composite (n=ab), and finding a divisor of 2ⁿ-1 (namely 2^a-1)

 

[mnc34829]

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

 

[sutupidmath]

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 $$2^n-1$$ be a prime number and n a number not relatively prime to it. Now, let $$p_1$$ be a prime divisor of n, and let k be the smallest positive integer for which $$p_1$$ divides $$2^k-1$$. Now from Fermat's little theorem we would get that $$p_1$$ is also a factor of $$2^{p_1-1}-1$$. Hence $$k\leq p_1-1<p_1.$$

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.