If n=p x q then
Mersenne's number 2n-1 can also be
cracked into two smaller numbers. The only bits
of algebra you need to know to follow the sequence
of equations are (1) A x ( B + C ) = A x B + A
x C; and (2) 2A x 2B = 2A+B.
| (2p-1) x (2pq-p +2pq-2p+…+2p +1) |
=2p
x (2pq-p +2pq-2p+…+2p
+1)
-(2pq-p +2pq-2p+…+2p
+1) |
= 2px2pq-p
+ 2px2pq-2p + …
+ 2px2p + 2p
- 2pq-p - 2pq-2p - …-
2p - 1 |
=2pq
+ 2pq-p +2pq-2p+…+2p
- 2pq-p - 2pq-2p - …-
2p - 1 |
| = 2pq
- 1= 2n-1. |
You will need to do a little playing around to
see why this works but it is quite satisfying
when you see that everything cancels out except
for the two expressions 2pq= 2p
x 2pq-p and -1.
|
