# Elementary number theory proof **URL:** \ **Category:** Factual Questions\ **Created:** [September 13, 2002, 4:57pm UTC](https://boards.straightdope.com/t/elementary-number-theory-proof/128314 "2002-09-13T16:57:43Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![KarlGauss](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/karlgauss/32/3713_2.png) [@KarlGauss](https://boards.straightdope.com/u/KarlGauss)\ **Post date:** [September 13, 2002, 4:57pm UTC](https://boards.straightdope.com/t/elementary-number-theory-proof/128314/1 "2002-09-13T16:57:43Z")
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] ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [September 13, 2002, 7:13pm UTC](https://boards.straightdope.com/t/elementary-number-theory-proof/128314/2 "2002-09-13T19:13:48Z")
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) ---
**Author:** ![panamajack](https://avatars.discourse-cdn.com/v4/letter/p/47e85d/32.png) [@panamajack](https://boards.straightdope.com/u/panamajack)\ **Post date:** [September 13, 2002, 7:25pm UTC](https://boards.straightdope.com/t/elementary-number-theory-proof/128314/3 "2002-09-13T19:25:25Z")
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. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [September 13, 2002, 7:30pm UTC](https://boards.straightdope.com/t/elementary-number-theory-proof/128314/4 "2002-09-13T19:30:51Z")
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](http://mathworld.wolfram.com/MersennePrime.html). There’s a direct connection between Mersenne Primes and even perfect numbers. A [perfect number](http://mathworld.wolfram.com/PerfectNumber.html) 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. ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [September 13, 2002, 8:53pm UTC](https://boards.straightdope.com/t/elementary-number-theory-proof/128314/5 "2002-09-13T20:53:39Z")
> [@](#): > > _Originally posted by Cabbage_ > We just proved that if 2p - 1 is prime, then p is prime. The converse is not true 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. ---
**Author:** ![KarlGauss](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/karlgauss/32/3713_2.png) [@KarlGauss](https://boards.straightdope.com/u/KarlGauss)\ **Post date:** [September 13, 2002, 9:37pm UTC](https://boards.straightdope.com/t/elementary-number-theory-proof/128314/6 "2002-09-13T21:37:59Z")
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](http://mathworld.wolfram.com/ProperDivisor.html))? ---
**Author:** ![KarlGauss](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/karlgauss/32/3713_2.png) [@KarlGauss](https://boards.straightdope.com/u/KarlGauss)\ **Post date:** [September 13, 2002, 9:44pm UTC](https://boards.straightdope.com/t/elementary-number-theory-proof/128314/7 "2002-09-13T21:44:21Z")
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. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [September 14, 2002, 7:30am UTC](https://boards.straightdope.com/t/elementary-number-theory-proof/128314/8 "2002-09-14T07:30:28Z")
> [@](#): > > Is there any reason you choose that definition? 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. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [September 14, 2002, 7:38am UTC](https://boards.straightdope.com/t/elementary-number-theory-proof/128314/9 "2002-09-14T07:38:06Z")
> [@](#): > > phi(n) = the number of positive integers less than n that are relatively prime to n (Euler Phi-function, or Euler totient function). 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.