Wacky residuals thread

[henryzz]

does anyone know about a program that can output the full residue from a rabin-miller test and not just the RES64

[michaf]

Originally Posted by MooooMoo

I'm not a vegetarian and have never been one, but keep in mind that I'll only give up beef if you find that residue. As Mini-Geek posted earlier, chicken, pork, lamb, fish, dairy products, etc are all fair game, so it wouldn't be that much of a lifestyle change for me.


Good luck if you're trying to find that "BEEF15BAD" residue, you'll need it

123*2^6786786871-1 is not prime. LLR Res64: 12BEEF15BAD431DE


Hmm... Rather interesting :) No more beef for MooMoo ;)
(Or else prove that the residue is incorrect....)

[Mini-Geek]

Originally Posted by michaf

(Or else prove that the residue is incorrect....)

Sure, just give me a few thousand years.

[gd_barnes]

Originally Posted by michaf

123*2^6786786871-1 is not prime. LLR Res64: 12BEEF15BAD431DE


Hmm... Rather interesting :) No more beef for MooMoo ;)
(Or else prove that the residue is incorrect....)

Oh come on now, you can do better than that!

123*2^6786786871-1 cannot possibly have a residue of 12BEEF15BAD431DE. It has factors of 7 AND 13!! As I recall, that would mean that it would have a residue of 0000000000000007!

(no joke)

HARDY HARDY HARDY HA HA HA HA HA !!!!!!!!!!!!!!!

Lest anyone wonder how I came up with that: My good old mainstay...Alpertron's site. All I did was calculate the values for all n=1 thru 30 and found the following patterns:

For all 123*2^n-1, all n==(1 mod 3) has a factor of 7 and all n==(7 mod 12) has a factor of 13. 6786786871 is both == (1 mod 3) and == (7 mod 12).

Mike, you can continue eating beef.

Sometimes I even amaze myself.


Gary

[michaf]

Originally Posted by gd_barnes

Oh come on now, you can do better than that!

123*2^6786786871-1 cannot possibly have a residue of 12BEEF15BAD431DE. It has factors of 7 AND 13!! As I recall, that would mean that it would have a residue of 0000000000000007!

(no joke)

HARDY HARDY HARDY HA HA HA HA HA !!!!!!!!!!!!!!!

Lest anyone wonder how I came up with that: My good old mainstay...Alpertron's site. All I did was calculate the values for all n=1 thru 30 and found the following patterns:

For all 123*2^n-1, all n==(1 mod 3) has a factor of 7 and all n==(7 mod 12) has a factor of 13. 6786786871 is both == (1 mod 3) and == (7 mod 12).

Mike, you can continue eating beef.

Sometimes I even amaze myself.


Gary

okok... I haven't had put any effort in it :)
I didn't even check for small factors :0

Continue to eat your beef :)

[Mini-Geek]

Originally Posted by gd_barnes

123*2^6786786871-1 cannot possibly have a residue of 12BEEF15BAD431DE. It has factors of 7 AND 13!! As I recall, that would mean that it would have a residue of 0000000000000007!

Can this be tested? LLR rejects anything with such a trivial factor, so what about something with a lowest factor that'd still fit in the residue size?

Originally Posted by gd_barnes

Lest anyone wonder how I came up with that: My good old mainstay...Alpertron's site. All I did was calculate the values for all n=1 thru 30 and found the following patterns:

For all 123*2^n-1, all n==(1 mod 3) has a factor of 7 and all n==(7 mod 12) has a factor of 13. 6786786871 is both == (1 mod 3) and == (7 mod 12).

Patterns != Proof, Law of Small Numbers, etc.
Do you have any mathematical proof (even if I couldn't understand it ) that all 123*2^n-1 with n==(1 mod 3) has a factor of 7 or that all n==(7 mod 12) has a factor of 13?

Originally Posted by gd_barnes

Mike, you can continue eating beef.

Oh, I'm sure he can for now anyway. Is there anything that can actually try to factor something that large to show certainly that it has trivial factors?

Originally Posted by gd_barnes

Sometimes I even amaze myself.

Oh Lord it's hard to be humble, when you're perfect in every way!

[S485122]

Originally Posted by Mini-Geek

Do you have any mathematical proof (even if I couldn't understand it ) that all 123*2^n-1 with n==(1 mod 3) has a factor of 7 or that all n==(7 mod 12) has a factor of 13?

n==1 mod 3.
n=3*m+1.
123*2^n-1=123*2^(3*m+1)-1=123*2*2^(3*m)-1
2^3==1 mod 7 => 2^(3*m)=(2^3)^m==1 mod 7
123*2*2^(3*m)-1==246*1-1 mod 7
245==0 mod 7

Use the same path for the other case.

Jacob

[henryzz]

Originally Posted by henryzz

does anyone know about a program that can output the full residue from a rabin-miller test and not just the RES64

i think this got buried

[gd_barnes]

Originally Posted by S485122

n==1 mod 3.
n=3*m+1.
123*2^n-1=123*2^(3*m+1)-1=123*2*2^(3*m)-1
2^3==1 mod 7 => 2^(3*m)=(2^3)^m==1 mod 7
123*2*2^(3*m)-1==246*1-1 mod 7
245==0 mod 7

Use the same path for the other case.

Jacob

Nicely stated. Call it the "law of modulo arithmetic".

[Mini-Geek]

Originally Posted by S485122

n==1 mod 3.
n=3*m+1.
123*2^n-1=123*2^(3*m+1)-1=123*2*2^(3*m)-1
2^3==1 mod 7 => 2^(3*m)=(2^3)^m==1 mod 7
123*2*2^(3*m)-1==246*1-1 mod 7
245==0 mod 7

Use the same path for the other case.

Jacob

Originally Posted by Mini-Geek

(even if I couldn't understand it )

Looks like that part turned out to be true (partially). I don't understand this part:

2^3==1 mod 7 => 2^(3*m)=(2^3)^m==1 mod 7

Why do we know that 2^(3*m)==1 mod 7 is equivalent to 2^3==1 mod 7? Is it just a law/thereom/whatever that there's no further explanation to or is there a reason that could be explained?

[S485122]

Originally Posted by Mini-Geek

Looks like that part turned out to be true (partially). I don't understand this part:

2^3==1 mod 7 => 2^(3*m)=(2^3)^m==1 mod 7

Why do we know that 2^(3*m)==1 mod 7 is equivalent to 2^3==1 mod 7? Is it just a law/thereom/whatever that there's no further explanation to or is there a reason that could be explained?

2^(3*m)=(2^3)^m
(2^3)^m=8^m
8^m=(7+1)^m
(7+1)^m==(0+1)^m mod 7
1^m=1
so
2^(3*m)==1 mod 7

Jacob