Special Form of Mersenne and Fermat Number Factors

[ewmayer]

As a moderator of the Math forum, I tried changing the title of this thread to something more descriptive - that's why Michael's initial post reads as having been last edited by me. (I only changed the subject: line, not the post content). Apparently the vBulletin software (unlike phpBB) doesn't change thread titles that way. Mike (Xyzzy), is there any way to change the thread title?

[GP2]

Originally posted by ewmayer
Apparently the vBulletin software (unlike phpBB) doesn't change thread titles that way. Mike (Xyzzy), is there any way to change the thread title?

Admin Options: Edit Thread should do it, no? (bottom of the page).

[ewmayer]

Originally posted by GP2
Admin Options: Edit Thread should do it, no? (bottom of the page).

Yep, that works. Thanks, Gord. That should make it easier for future users to find the thread via any set of the obvious search options for this topic.

[michael]

I haven't figured out yet why j=0mod2, but i came up with something else that i found worth mentioning.

Continuing the letters used in this threat:
If F(n)=2^(2^p)+1 is composite and you call it's divisors qi=ji*2^(n+1)+1 (i=1,2,...) then the product over all the qi's you get:
F(n)=product(ji)*2^(2n+2)+sum(ji)*2^(n+1)+1 (i=1,2,...) (A)
We also have that:
F(n)=1mod2^(2n+2) (B)

(A)+(B) conclude that
sum(ji)*2^(n+1)=0mod2^(2n+2)
or sum(ji)=0mod2^(n+1)

Example for F(5)=641*6700417:
641=10*2^6 + 1
6700417=104694*2^6 + 1
and 10+104694=818*2^6

I don't believe much before i see a proof, but if you take j=0mod2 then you can conclude further that sum(ji)=0mod2^(n+2)

"Off topic" I never knew it was this tough ...typing... math, sthing that took me 3 minutes to write down on paper took approx 15 mts to type and still it doesn't look "maths". Could someone please explain me how to use exponents and indices? And is it even possible to use Pi and Sigma in greek notation (which are widely used as symbols for product and sum)?

-michael

[GP2]

Originally posted by michael
"Off topic" I never knew it was this tough ...typing... math, sthing that took me 3 minutes to write down on paper took approx 15 mts to type and still it doesn't look "maths". Could someone please explain me how to use exponents and indices? And is it even possible to use Pi and Sigma in greek notation (which are widely used as symbols for product and sum)?

For superscripts and subscripts, you can use [ sup ] and [ /sup ] and [ sub ] and [ /sub ] (except without the spaces around the brackets).

In HTML, you could use & Sigma ; and & Pi ; (again without the spaces around the & and the ; ), but this board software might not allow it (and even if it did, many people wouldn't see Greek letters because of browser or font issues).

Testing: Σ ... Π

[Xyzzy]

You could type it all into Mathematica, Maple or even Word formula editor and attach the image...

[GP2]

Originally posted by GP2
In HTML, you could use & Sigma ; and & Pi ;
[...]
Testing: Σ ... Π

This fails under Mozilla, for some reason it produces a capital Z instead of a capital Sigma.
And also, it's the size of a regular capital letter, whereas you really want something a little larger.

However, if you use
& sum ; and & prod ;
I think it will work:

Testing:

∑ a_i xⁱ

∏ a_ib_i

[GP2]

Testing Euler gamma:

& gamma ;

Testing:
γ = 0.57721566490153286...
e^γ

[only_human]

Testing the equivalence symbol that's also used for congruence

& #8801 ;
≡

& equiv ;
≡

U_p ≡ (3/p) (mod p)
P ≡ 1 (mod 4)

[JoCo]

I know that we can eliminate most numbers while trying to factor a Mersenne. ( A factor must be in the form 2kp+1, it must be 1 or 7 MOD 8, and must be prime. )

But is there a similar pattern that factors must have for numbers in the form N * 2^p-1 +/- 1 ( Even if it only works on N * 2^p+1 or only with N*2^p-1, I'd like to know ) ?



JoCo

[michael]

Grrrrr Now that i typed it all out, i noticed that i actually didn't prove what Lucas said, though this is a more elementary proof (without groupe theorem) of the initial assumption. I will investigate further....and well, i did prove sthing for other bases than 2

Too much work to just simply delete it

Lemma:
For any odd prime p that doesn't devide a: If a² + 1 ≡ 0 mod p then p ≡ 1 mod 4

Proof: Suppose this isn't always the case, so imagine p=4k + 3

(1) Flt (Fermat litte theorem) gives a^p-1 - 1 ≡ 0 mod p and therefor a^4k+2 - 1 ≡ 0 mod p

(2)Since a² + 1 divides p this product
(a² + 1)(a^4k - a^4k-2 +a^4k-4 - ... +a⁴ - a² +1)=a^4k+2 + 1
will also be ≡ 0 mod p

(1) + (2) gives that p devides both a^4k+2 - 1 and a^4k+2 + 1
So p=2, a contradiction and p must be of the form p=4k + 1

Which proves this lemma

Now look at a⁴ + 1 and p mod 8. Cause of the previous lemma and a⁴ + 1 = a^2[sup]2[/sup] + 1 , the only leftovers are p ≡ 1 mod 8 and p ≡ 5 mod 8

Same reasoning gives
(1) a^4k+2 - 1 ≡ 0 mod p;
(2) (a⁴ + 1)(a^8k - a^8k-4 +a^8k-8 - ... +a⁸ - a⁴ +1)=a^8k+2 + 1 ≡ 0 mod p
Which results in a likewise contradiction so p=8k + 1

It's easy to see that for every a^2[sup]n[/sup] + 1 we only need to check p=2ⁿ⁺¹k + (2ⁿ + 1) and rule out this possibility using the same strategy over and over so p=2ⁿ⁺¹k + 1.

Take a=2 then u see that if p devides 2^2[sup]n[/sup] + 1, then p=2ⁿ⁺¹k+1

-michael