Math Is Fun Forum

Primenumbers

Member

Registered: 2013-01-22

Posts: 149

Which Mersenne Number is this number a factor of? Proof

Whatever done to a Mersenne number to get to zero must be able to be done to it’s factors.

Mersenne Number= 2^11 -1
Factors = 23 and 89
2^11 -1 takes eleven goes to get to zero if I continually minus one and divide by 2. Watch what happens to 23 and 89 acting as remainders as I do the same to them.

2^11 -1
2^10 -1           First go
2^9 -1            Second go
2^8 -1            Third go
2^7 -1             Fourth go
2^6 -1             Fifth go
2^5 -1             Sixth go
2^4 -1             Seventh go
2^3 -1             Eighth go
2^2 -1             Ninth go
2-1                  Tenth go
1-1=0              Eleventh go

23
(23-1)/2 = 11                                First go
(11-1)/2 = 5                                  Second go
(5-1)/2 = 2                                   Third go
23+2 = 25, (25-1)/2 = 12           Fourth go
23+12 = 35, (35-1)/2 = 17         Fifth go
(17-1)/2 = 8                                  Sixth go
23+8 = 31, (31-1)/2 = 15            Seventh go
(15-1)/2 = 7                                  Eighth go
(7-1)/2 = 3                                    Ninth go
(3-1)/2 = 1                                    Tenth go
(1-1)/2 = 0                                     Eleventh go

89
8(89-1)/2 = 44                                  First go
89+44 = 133, (133-1/2) = 66       Second go
89+66 = 155, (155-1)/2 = 77       Third go
(77-1)/2 = 38                                  Fourth go
89+38 = 127, (127-1)/2 = 63        Fifth go
(63-1)/2 = 31                                  Sixth go
(31-1)/2 = 15                                   Seventh go
(15-1)/2 = 7                                     Eighth go
(7-1)/2 = 3                                       Ninth go
(3-1)/2 = 1                                       Tenth go
(1-1)/2 = 0                                        Eleventh go

They both take eleven goes to get to zero too.

Working backwards it can be seen that this must be the case. Starting with zero I multiply by 2 and add one continually until I get to 2^11 -1. The  same must be done to the remainders which will then become 23 and 89 or zero, the factors of 2^11 -1.

Let the number of goes an odd number, y, takes to get to zero by continually minusing one and dividing by 2, (adding y when even) =z.

The z for 2^11 -1, 23 and 89 =11.

Whatever z equals for y, 2^z -1 must be factorable by y. When we use the method for 2^z -1, we never add 2^z -1 as it never equals an even number. This could potentially alter remainders for potential factors, but for Mersenne Numbers, this is not the case.

---

"Time not important. Only life important." - The Fifth Element 1997