Wacky residuals thread

[Mini-Geek]

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

Okay, following it so far...

(7+1)^m==(0+1)^m mod 7

How is the 7 eliminated so we know that 8^m==1^m?

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

And the rest makes sense, so it's just that one part I'm confused on.

[gd_barnes]

Originally Posted by Mini-Geek

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

Okay, following it so far...

(7+1)^m==(0+1)^m mod 7

How is the 7 eliminated so we know that 8^m==1^m?

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

And the rest makes sense, so it's just that one part I'm confused on.

Think of it like this:

(7+1) == (1 mod 7)
-and-
(0+1) == (1 mod 7)

therefore x represents the same integer 0<=x<=6 in both of the following:
(7+1)^m == (x mod 7)
-and-
(0+1)^m == (x mod 7)

therefore:
(7+1)^m == (0+1)^m mod 7

therefore:
8^m == 1^m mod 7

[S485122]

Originally Posted by Mini-Geek

(7+1)^m==(0+1)^m mod 7

How is the 7 eliminated so we know that 8^m==1^m?

1 == 8 == -6 == 15 == -13 mod 7 is the same as saying 1, 8, -6, 15 and -13 are multiples of 7 plus 1.

If we compute (7+1)^m = 7^m+m*7^(m-1)*1+ ... +m*7*1^(m-1)+1^m all terms except 1^m contain a power of 7 greater than 0. So we can say that (7+1)^m is a multiple of 7 plus 1.

More generally : (a*n+b)^m == b^m mod n. You could lookup some more explanation about modular arithmetics...

Jacob

[Jens K Andersen]

From an unrelated PFGW search:
204912863*2^33333-2147 is composite: RES64: 69ED3420123456F2 (1.9872s+0.0003s)
Not that much for a 2s test.

[MooooMoo]

I got 8 A's in one residue:

313*2^919519-1 is not prime. LLR Res64: B9AA9AE1AAAD1AAD Time : 1317.195 sec.

[kar_bon]

other 8er's:

1199*2^198096-1 is not prime. LLR Res64: CCBCCCF57770CCC0
1179*2^76893-1 is not prime. LLR Res64: 6C1D14411111CA41
1135*2^139165-1 is not prime. LLR Res64: C656B5A966666D76
1165*2^138973-1 is not prime. LLR Res64: F49A8666A66666F0
1179*2^170264-1 is not prime. LLR Res64: A8A2C562AAAAAA6E

the last one with 6 A's in a row!

[MyDogBuster]

3311*2^101894-1 CCCCCAC8484CF1AF 29.088 (Nice start)
10096*45^112584-1 93663508540e5a65 4912.17 (Almost all numeric)
10096*45^36114-1 df8a177777509fac 230.17 (Craps anyone)

[henryzz]

Originally Posted by henryzz

a list up to n=1000 made using llr's predecessor prp

4259877765*2^4+1
4259877765*2^10+1
4259877765*2^16+1
4259877765*2^139+1
4259877765*2^142+1
4259877765*2^328+1
4259877765*2^415+1
4259877765*2^583+1
4259877765*2^868+1
4259877765*2^883+1

these numbers are all prime:

(4259877765*2^4+1)/7
(4259877765*2^10+1)/7
(4259877765*2^16+1)/7
(4259877765*2^139+1)/7
(4259877765*2^142+1)/7
(4259877765*2^328+1)/7
(4259877765*2^415+1)/7
(4259877765*2^583+1)/7
(4259877765*2^868+1)/7
(4259877765*2^883+1)/7

edit:
it works the other way as well i searched for primes of the form "(4259877765*2^n+1)/7" up to n=10k and then checked the residue for "(4259877765*2^n+1)" and it was always the same
edit2: just realised that the numbers all have the same residue to each other in other prp bases as well though different to 3-prp

i just found this:
http://www.primenumbers.net/Renaud/eng/fermat1.html
it explains why lots of numbers have the same residues

time to repeat my question:
does anyone know of a prp program that can display the full residue not just the RES64?
i could then use it to find prps hopefully
i expect the answer to be no but i would quite like a response

[Cruelty]

I've searched all my residues for the sequences of at least 6 digits / letters of the same kind:

1515*2^618318-1 is not prime.  LLR Res64: 5461D351111114AF --> 6 x 1
25*2^695867-1 is not prime.  LLR Res64: 7D382AE72222229E --> 6 x 2
59*2^1625132-1 is not prime.  LLR Res64: E3CAA3333333171E --> 7 x 3
736320585*2^715845-1 is not prime.  LLR Res64: 9604AF6744444483 --> 6 x 4
2*3^184602-1 is not prime.  RES64: 214E3DFFA875B519.  OLD64: B59B17A74A777777 --> 6 x 7
736320585*2^93318-1 is not prime.  LLR Res64: 18106436ABBBBBBA --> 6 x B

[mdettweiler]

Here's an interesting one that showed up today:

424*93^64337-1 is composite: RES64: [CAFFBBEEEA1063A4] (381.0392s+0.0157s)

[mdettweiler]

Just now I was doing an off-the-wall search for MooMoo's "BEEF15BAD" residue with very small numbers (a fixed n search for k=3-1G, n=5, k*2^n+1), when I noticed a very weird pattern:

168195*2^5+1 = 5382241 is prime! (trial divisions)
168221*2^5+1 = 5383073 is prime! (trial divisions)
168225*2^5+1 = 5383201 is prime! (trial divisions)
168231*2^5+1 = 5383393 is prime! (trial divisions)
168239*2^5+1 = 5383649 is prime! (trial divisions)
168245*2^5+1 = 5383841 is prime! (trial divisions)
168251*2^5+1 = 5384033 is prime! (trial divisions)
168269*2^5+1 = 5384609 is prime! (trial divisions)
168281*2^5+1 = 5384993 is prime! (trial divisions)
168293*2^5+1 = 5385377 is prime! (trial divisions)
168305*2^5+1 = 5385761 is prime! (trial divisions)

This continues such that every number so far in my sieve file is prime. (I stopped the LLR testing at that point since I figured it was a pointless exercise, considering that it wouldn't be able to produce any composites and therefore useful residues.)

I'm sure there's a simple mathematical explanation for what I'm seeing here. You know, though I hate to sound "crankish"...if there is a simple mathematical proof that all k*2^5+1 are prime, then this could lead to a very simple way to find a 100 million digit prime that would qualify for the EFF prize! Heck on spending 3+ years per number searching 100 million digit numbers through GIMPS when you can just find one this way. (Of course, I'm sure there's something I'm missing that would preclude this, otherwise someone would have won the prize by now.)

Edit: I'm seeing this on k*2^7+1 as well.