I'm trying to understand why the Euclid-Euler theorem implies a one-to-one correspondence between Mersenne primes and perfect numbers.
Theorem 1 (Euclid):
- If $2^{p}−1$ is a Mersenne prime, then $2^{p−1}⋅(2^{p}−1)$ is perfect.
Theorem 2 (Euler):
- If $n$ is even and perfect, then there is a Mersenne prime $2^{p}−1$ such that $n = 2^{p−1}(2^{p}−1)$.
Wikipedia and other sources I've come across say that these two theorems together imply a "one-to-one relationship between even perfect numbers and Mersenne primes; each Mersenne prime generates one even perfect number, and vice versa."
But it's not intuitive to me why Theorem 2 is the converse of Theorem 1, since we cannot rule out odd perfects. I would prefer to instead verify this using logic rules, but don't know how to express Theorem 2 as a formula.
Assuming the universe of discourse is the natural numbers, if I let
- M(x) = "x is a Mersenne prime"
- P(x) = "x is a perfect number"
- E(x) = "x is even"
...then I can write Theorem 1 as $\forall p(M(2^{p}−1) \rightarrow P(2^{p−1}(2^{p}−1))$.
But how do I go about expressing Theorem 2 in this way?
I tried the following
$\forall n[(E(n) \land P(n)) \rightarrow \exists p(M(2^{p}−1) \land n = 2^{p−1}(2^{p}−1))]$
...but I doubt this is correct and I'm not sure where to go from here.
EDIT: Someone very helpfully pointed out that the first theorem implies that $2^{p−1}(2^{p}−1)$ is also even (in addition to being perfect), since $p$ is prime and therefore the exponent is at least 1.
Here's my new attempt:
Assume the universe is the natural numbers and let $M(w)$, $P(w)$ and $E(w)$ stand for the following statements:
- $M(w)$ – “w is Mersenne prime”
- $P(w)$ – “w is perfect”
- $E(w)$ – “w is even”
Then I can write Theorem 1 as:
$$∀x[M(2^x - 1) \rightarrow \exists y(y = 2^{x-1}(2^x – 1) ∧ P(y) ∧ E(y))]$$
...and Theorem 2 as:
$$∀x[∃y(y = 2^{x-1}(2^x – 1) ∧ P(y) ∧ E(y)) \rightarrow M(2^x - 1)]$$
But is this equivalent to the statement given above that "If $n$ is even and perfect, then there is a Mersenne prime $2^{p}−1$ such that $n = 2^{p−1}(2^{p}−1)$"? I'm not sure if I've expressed the consequent properly.