To call this number theory is a stretch, but I needed to get your attention!
I read recently that the following statement is “trivial”:
If N is composite then 2[sup]N[/sup] - 1 is composite.
I am more than embarrassed to admit that the proof of this “trivial” statement eludes me (although for N even, it’s easy using differences of squares)
[sub][sup]Thanks
- Karl (who doesn’t deserve his moniker)[/sup][/sub]
2[sup]ab[/sup] - 1 = (2[sup]a[/sup] - 1)(2[sup]a(b-1)[/sup] + 2[sup]a(b-2)[/sup] + … + 2[sup]a[/sup] + 1)
No offense, but it’d be kind of funny if you’d proven this somewhere in your Disquisitiones Arithmeticae and then forgot about it now.
I had a longer post with solution, but Cabbage has given it quite succintly.
Also, some more info on these types of numbers:
We just proved that if 2[sup]p[/sup] - 1 is prime, then p is prime. The converse is not true, but primes of the form 2[sup]p[/sup] - 1 are called Mersenne Primes.
There’s a direct connection between Mersenne Primes and even perfect numbers. A perfect number is a number such that the sum of its divisors is twice the original number; for example, six is perfect, since 1+2+3+6=12, or twice six. Every even perfect number is of the form
(2[sup]p[/sup] - 1)(2[sup]p-1[/sup])
with 2[sup]p[/sup] - 1 a Mersenne prime.
No one knows how many even perfect numbers there are (or how many Mersenne primes, obviously). No one knows if there are any odd perfect numbers.
The first counter-example to the converse is p = 11: 2[sup]11[/sup] - 1 = 2047 = 23[symbol]´[/symbol]89.
More generally: if p is a prime of the form 4k+3 then 2p+1 is prime if and only if it divides 2[sup]p[/sup] - 1.
Many thanks.
And, by the way Cabbage, I notice that you define a perfect number “such that the sum of its divisors is twice the original number”. Is there any reason you choose that definition (i.e. why not "the sum of its proper divisors)?
I forgot to say, panamajack, that ever since the real Karl’s 200th birthday, I’m not as sharp as I used to be. The last twenty-five years have been pretty much a math write-off.
Yeah, there is. Along these lines, you can define two functions on the positive integers:
f(n) = the sum of the divisors of n, or
g(n) = the sum of the proper divisors of n.
Then n is perfect if and only if f(n)=2n if and only if g(n)=n.
But f behaves more nicely than g, so I think it’s easier to work with f. In particular, f is multiplicative, while g is not.
(Multiplicative meaning f(mn)=f(m)f(n), when m and n are relatively prime).
For example:
f(42) = 1+2+3+6+7+14+21+42 = 96
f(6)*f(7) = (1+2+3+6)(1+7) = 96 also.
But:
g(42) = 54, while
g(6)*g(7) = (1+2+3)(1) = 6.
It’s also easier to define such things as superperfect numbers in terms of f.
n is superperfect if and only if f(f(n)) = 2n. 16 is superperfect since
f(f(16)) = f(31) = 32.
Finally, let’s throw in a couple more functions:
phi(n) = the number of positive integers less than n that are relatively prime to n (Euler Phi-function, or Euler totient function).
h(n) = the number of positive divisors of n.
There’s a connection among all three of these functions (f, phi, and h). I couldn’t find it on the net, so I’m going from memory here, but I think the connection is:
f(n) = SUM [h(d)phi(n/d)]
where the sum runs over all d such that d is a positive divisor of n.
I just realized that’s misleading. It really should be “the number of positive integers less than or equal to n that are relatively prime to n” so that we get phi(1)=1, as it should be.