# Homework Help: Euclid's formula

1. Jan 30, 2010

### imprank6

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

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

3. The attempt at a solution

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

2. Jan 30, 2010

### VeeEight

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)

3. Jan 30, 2010

### 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

4. Jan 31, 2010

### 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!