2 holes in bizarre theorem about composite Mersenne Numbers

[CRGreathouse]

I see you have learned the joy of counterexamples!

[wildrabbitt]

[science_man_88]

Originally Posted by wildrabbitt

ie 8mp + 1 and (8m - 2)p + 1 ?

see the thread I posted about k values using modular arithmetic you can prove results that can't fit the choice of factor af a mersenne number with prime exponent. take p=4j+1:

we have four cases mod 4:



and you can generalize this to cases 0,p,-p,2 mod 4.

[wildrabbitt]

I was looking at that thread just before you posted as it happens.


What you've said with those 4 lines is

For p congruent to 1 mod 4, a factor of 2^p - 1 of the form 2kp + 1 can only exist for

k congruent to 0 (mod 4)
k congruent to 3 (mod 4)

as 2kp + 1 must be 1 or 7 (mod 8)

if I understand correctly.

Big thanks for that post scienceman. It's given me an idea for something

[science_man_88]

Originally Posted by wildrabbitt

I was looking at that thread just before you posted as it happens.


What you've said with those 4 lines is

For p congruent to 1 mod 4, a factor of 2^p - 1 of the form 2kp + 1 can only exist for

k congruent to 0 (mod 4)
k congruent to 3 (mod 4)

as 2kp + 1 must be 1 or 7 (mod 8)

if I understand correctly.

Big thanks for that post scienceman. It's given me an idea for something

and the generalization is that:
k congruent to 0 or -p mod 4 are the possible k values that produce possible factors.

you can also use what I talked about above and show for example that for no prime p will k=2p+2 produce a prime.

[wildrabbitt]

and the generalization is that:
k congruent to 0 or -p mod 4 are the possible k values that produce possible factors.

So 2kp + 1 divides 2^p - 1 if and only if k is congruent to 0 or -p (mod 4).

That's amazing, if I've understood correctly.

If p is 1 mod 4 then k must be 0 or -p (mod 4) is 0 or -(4k + 1) ie 3 mod 4.
If p is 3 mod 4 then k must be 0 or -p (mod 4) is 0 or -(4k + 3) ie 1 mod 4.

[wildrabbitt]

and the generalization is that:
k congruent to 0 or -p mod 4 are the possible k values that produce possible factors.

Would the proof of this be like the specific case you gave :

we have four cases mod 4:

but Starting with we have p cases (mod p)???

[science_man_88]

Originally Posted by wildrabbitt

So 2kp + 1 divides 2^p - 1 if and only if k is congruent to 0 or -p (mod 4).

That's amazing, if I've understood correctly.

If p is 1 mod 4 then k must be 0 or -p (mod 4) is 0 or -(4k + 1) ie 3 mod 4.
If p is 3 mod 4 then k must be 0 or -p (mod 4) is 0 or -(4k + 3) ie 1 mod 4.

only k with these properties produce candidates that could be factors of a given mersenne. edit: see CRG's post below having these properties doesn't guarantee it's a divisor.

also since a negative sign out front is multiplication by -1 we get -4k-1 and -4k-3 since 4k divides by 4 regardless we get -1 and -3 and then using the property that -(-x) in modular arithmetic mod n is congruent to n-x we get 3 and 1 respectively so k must be 0 or 3 mod 4 for p that are 1 mod 4 and 0 and 1 for p that are 3 mod 4.

Originally Posted by wildrabbitt

Would the proof of this be like the specific case you gave :

but Starting w have p cases (mod p)???

we have 4 cases possible still working mod 4 ( with usefulness dependent on p):

2(4k)p+1 = 1 mod 8
2(4k+1)p = 2p+1 mod 8 ( and since modular math allows you to multiply and get to another remainder mod a different number potentially) we have 2(4k+1)(4j+1)+1 = (8k+2)(4j+1)+1 = 32kj+8k+8j+3 = 3 mod 8 =2(4k+3)(4j+3)+1 = (8k+6)(4j+3)+1 = 32kj+24k+24j+19 = 19 mod 8 = 19-16 mod 8 = 3 mod 8. this is the k=p mod 4 case.
2(4k+1)p = 2p+1 mod 8 ( and since modular math allows you to multiply and get to another remainder mod a different number potentially) we have 2(4k+1)(4j+3)+1 = (8k+2)(4j+3)+1 = 32kj+24k+8j+7 = 7 mod 8 this is the k=-p mod 4 case. one one is shown because when they are opposites they can switch around and have the same algebraic value ( to within the switching places of variable names).
2(4k+2)p+1 = (8k+4)(4j+1)+1 which mod 8 simplifies to 4(4j+1)+1 = 16j+5 = 5 mod 8.

[CRGreathouse]

Originally Posted by wildrabbitt

So 2kp + 1 divides 2^p - 1 if and only if k is congruent to 0 or -p (mod 4).

That's amazing, if I've understood correctly.

If p is 1 mod 4 then k must be 0 or -p (mod 4) is 0 or -(4k + 1) ie 3 mod 4.
If p is 3 mod 4 then k must be 0 or -p (mod 4) is 0 or -(4k + 3) ie 1 mod 4.

I think sm intended it to be interpreted as "only if", not "if and only if".

[chalsall]

Originally Posted by CRGreathouse

I think sm intended it to be interpreted as "only if", not "if and only if".

What about not and if?

[science_man_88]

Originally Posted by chalsall

What about not and if?

why don't I just go with necessary but not sufficient. as the conditions are necessary for 2kp+1 to be a divisors for 2^p-1 but they are hardly sufficient.