## Thanks to all. Proposed binary Prime number test fails.

Expand Messages
• Two prime numbers which are known to make this test fail: 2^(n-1) mod n 1093 and 3511, Thanks to Alan for the link,
Message 1 of 18 , May 23, 2007
Two prime numbers which are known to make this test fail: 2^(n-1) mod n

1093 and 3511,

Thanks to Alan for the link, http://www.research.att.com/~njas/sequences/A001567

----------

No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.5.467 / Virus Database: 269.7.6/815 - Release Date: 5/22/07 3:49 PM

[Non-text portions of this message have been removed]
• ... They don t make the test fail. They satisfy a stronger condition: 2^(n-1) ==1 (mod n^2) They are the only known Wieferich primes:
Message 2 of 18 , May 23, 2007
Paul E. Schippnick wrote:
> Two prime numbers which are known to make this test fail: 2^(n-1) mod n
>
> 1093 and 3511,

They don't make the test fail. They satisfy a stronger condition:
2^(n-1) ==1 (mod n^2)
They are the only known Wieferich primes:
http://mathworld.wolfram.com/WieferichPrime.html
"Normal" (non-Wieferich) primes only satisfy Fermat's little Theorem:
2^(n-1) ==1 (mod n)

--
Jens Kruse Andersen
• I rechecked the result for 1093 and also did 3511. Both passed. I must have made a mistake using the calculator. 2^(n-1)-1 mod n The reason I called this a
Message 3 of 18 , May 24, 2007
I rechecked the result for 1093 and also did 3511. Both passed. I
must have made a mistake using the calculator.

2^(n-1)-1 mod n

The reason I called this a binary test for prime is that the number
in binary 2^(n-1)-1 has all the bits set to one. And that the number
of bits set are one less place than the prime number, and has that
prime number as one of its prime factors.

And because Mersenne numbers [2^p - 1] in binary are the number of
bits as its power set to one, that they all whether prime or not will
test as if prime using that method.

--- In primenumbers@yahoogroups.com, "Jens Kruse Andersen"
<jens.k.a@...> wrote:
>
> Paul E. Schippnick wrote:
> > Two prime numbers which are known to make this test fail: 2^(n-1)
mod n
> >
> > 1093 and 3511,
>
> They don't make the test fail. They satisfy a stronger condition:
> 2^(n-1) ==1 (mod n^2)
> They are the only known Wieferich primes:
> http://mathworld.wolfram.com/WieferichPrime.html
> "Normal" (non-Wieferich) primes only satisfy Fermat's little
Theorem:
> 2^(n-1) ==1 (mod n)
>
> --
> Jens Kruse Andersen
>
• Are there any more after 3511?
Message 4 of 18 , May 30, 2007
Are there any more after 3511?
• ... From: mistermac39 [mailto:mistermac39@hotmail.com] ... I scanned a long way out with repetitive patterns and failed to find any more base 2 Wieferich
Message 5 of 18 , May 30, 2007
-----Original Message-----
From: mistermac39 [mailto:mistermac39@...]

> Are there any more after 3511?

I scanned a long way out with repetitive patterns and failed to find any
more 'base 2' Wieferich primes.

However similar primes exist in other bases b, such that both p and p^2
divide b^p-1. I attach a list of some of these from base 2 to 229.

Often it can be seen that p divides b^(p/x)-1, in these cases it seems that
p^2 will divide that same number.

This raises the following question. Is it the case that where both p and p^2
divide b^p-1 and p divides (for some x) b^(p/x)-1 that p^2 will also divide
the same number. Can this be proved, or even conjectured, either way?

Regards,

Kevin.

--- Base 2 ---
1093 divides 2^364-1, 1093^2 divides 2^364-1
1093 divides 2^728-1, 1093^2 divides 2^728-1
1093 divides 2^1092-1, 1093^2 divides 2^1092-1
3511 divides 2^1755-1, 3511^2 divides 2^1755-1
3511 divides 2^3510-1, 3511^2 divides 2^3510-1
--- Base 3 ---
11 divides 3^5-1, 11^2 divides 3^5-1
11 divides 3^10-1, 11^2 divides 3^10-1
1006003 divides 3^1006002-1, 1006003^2 divides 3^1006002-1
--- Base 5 ---
20771 divides 5^10385-1, 20771^2 divides 5^10385-1
20771 divides 5^20770-1, 20771^2 divides 5^20770-1
40487 divides 5^40486-1, 40487^2 divides 5^40486-1
--- Base 7 ---
5 divides 7^4-1, 5^2 divides 7^4-1
491531 divides 7^245765-1, 491531^2 divides 7^245765-1
491531 divides 7^491530-1, 491531^2 divides 7^491530-1
--- Base 11 ---
71 divides 11^70-1, 71^2 divides 11^70-1
--- Base 13 ---
863 divides 13^862-1, 863^2 divides 13^862-1
1747591 divides 13^873795-1, 1747591^2 divides 13^873795-1
1747591 divides 13^1747590-1, 1747591^2 divides 13^1747590-1
--- Base 17 ---
3 divides 17^2-1, 3^2 divides 17^2-1
46021 divides 17^7670-1, 46021^2 divides 17^7670-1
46021 divides 17^15340-1, 46021^2 divides 17^15340-1
46021 divides 17^23010-1, 46021^2 divides 17^23010-1
46021 divides 17^30680-1, 46021^2 divides 17^30680-1
46021 divides 17^38350-1, 46021^2 divides 17^38350-1
46021 divides 17^46020-1, 46021^2 divides 17^46020-1
48947 divides 17^24473-1, 48947^2 divides 17^24473-1
48947 divides 17^48946-1, 48947^2 divides 17^48946-1
--- Base 19 ---
3 divides 19^1-1, 3^2 divides 19^1-1
3 divides 19^2-1, 3^2 divides 19^2-1
7 divides 19^6-1, 7^2 divides 19^6-1
13 divides 19^12-1, 13^2 divides 19^12-1
43 divides 19^42-1, 43^2 divides 19^42-1
137 divides 19^68-1, 137^2 divides 19^68-1
137 divides 19^136-1, 137^2 divides 19^136-1
--- Base 23 ---
13 divides 23^6-1, 13^2 divides 23^6-1
13 divides 23^12-1, 13^2 divides 23^12-1
2481757 divides 23^827252-1, 2481757^2 divides 23^827252-1
2481757 divides 23^1654504-1, 2481757^2 divides 23^1654504-1
2481757 divides 23^2481756-1, 2481757^2 divides 23^2481756-1
13703077 divides 23^13703076-1, 13703077^2 divides 23^13703076-1
--- Base 29 ---
--- Base 31 ---
7 divides 31^6-1, 7^2 divides 31^6-1
79 divides 31^39-1, 79^2 divides 31^39-1
79 divides 31^78-1, 79^2 divides 31^78-1
6451 divides 31^3225-1, 6451^2 divides 31^3225-1
6451 divides 31^6450-1, 6451^2 divides 31^6450-1
2806861 divides 31^467810-1, 2806861^2 divides 31^467810-1
2806861 divides 31^935620-1, 2806861^2 divides 31^935620-1
2806861 divides 31^1403430-1, 2806861^2 divides 31^1403430-1
2806861 divides 31^1871240-1, 2806861^2 divides 31^1871240-1
2806861 divides 31^2339050-1, 2806861^2 divides 31^2339050-1
2806861 divides 31^2806860-1, 2806861^2 divides 31^2806860-1
--- Base 37 ---
3 divides 37^1-1, 3^2 divides 37^1-1
3 divides 37^2-1, 3^2 divides 37^2-1
77867 divides 37^77866-1, 77867^2 divides 37^77866-1
--- Base 41 ---
29 divides 41^4-1, 29^2 divides 41^4-1
29 divides 41^8-1, 29^2 divides 41^8-1
29 divides 41^12-1, 29^2 divides 41^12-1
29 divides 41^16-1, 29^2 divides 41^16-1
29 divides 41^20-1, 29^2 divides 41^20-1
29 divides 41^24-1, 29^2 divides 41^24-1
29 divides 41^28-1, 29^2 divides 41^28-1
1025273 divides 41^1025272-1, 1025273^2 divides 41^1025272-1
--- Base 43 ---
5 divides 43^4-1, 5^2 divides 43^4-1
103 divides 43^102-1, 103^2 divides 43^102-1
--- Base 47 ---
--- Base 53 ---
3 divides 53^2-1, 3^2 divides 53^2-1
47 divides 53^23-1, 47^2 divides 53^23-1
47 divides 53^46-1, 47^2 divides 53^46-1
59 divides 53^29-1, 59^2 divides 53^29-1
59 divides 53^58-1, 59^2 divides 53^58-1
97 divides 53^48-1, 97^2 divides 53^48-1
97 divides 53^96-1, 97^2 divides 53^96-1
--- Base 59 ---
2777 divides 59^1388-1, 2777^2 divides 59^1388-1
2777 divides 59^2776-1, 2777^2 divides 59^2776-1
--- Base 61 ---
--- Base 67 ---
7 divides 67^3-1, 7^2 divides 67^3-1
7 divides 67^6-1, 7^2 divides 67^6-1
47 divides 67^46-1, 47^2 divides 67^46-1
268573 divides 67^134286-1, 268573^2 divides 67^134286-1
268573 divides 67^268572-1, 268573^2 divides 67^268572-1
--- Base 71 ---
3 divides 71^2-1, 3^2 divides 71^2-1
47 divides 71^23-1, 47^2 divides 71^23-1
47 divides 71^46-1, 47^2 divides 71^46-1
331 divides 71^165-1, 331^2 divides 71^165-1
331 divides 71^330-1, 331^2 divides 71^330-1
--- Base 73 ---
3 divides 73^1-1, 3^2 divides 73^1-1
3 divides 73^2-1, 3^2 divides 73^2-1
--- Base 79 ---
7 divides 79^3-1, 7^2 divides 79^3-1
7 divides 79^6-1, 7^2 divides 79^6-1
263 divides 79^262-1, 263^2 divides 79^262-1
3037 divides 79^3036-1, 3037^2 divides 79^3036-1
1012573 divides 79^1012572-1, 1012573^2 divides 79^1012572-1
--- Base 83 ---
4871 divides 83^487-1, 4871^2 divides 83^487-1
4871 divides 83^974-1, 4871^2 divides 83^974-1
4871 divides 83^1461-1, 4871^2 divides 83^1461-1
4871 divides 83^1948-1, 4871^2 divides 83^1948-1
4871 divides 83^2435-1, 4871^2 divides 83^2435-1
4871 divides 83^2922-1, 4871^2 divides 83^2922-1
4871 divides 83^3409-1, 4871^2 divides 83^3409-1
4871 divides 83^3896-1, 4871^2 divides 83^3896-1
4871 divides 83^4383-1, 4871^2 divides 83^4383-1
4871 divides 83^4870-1, 4871^2 divides 83^4870-1
13691 divides 83^6845-1, 13691^2 divides 83^6845-1
13691 divides 83^13690-1, 13691^2 divides 83^13690-1
--- Base 89 ---
3 divides 89^2-1, 3^2 divides 89^2-1
13 divides 89^12-1, 13^2 divides 89^12-1
--- Base 97 ---
7 divides 97^2-1, 7^2 divides 97^2-1
7 divides 97^4-1, 7^2 divides 97^4-1
7 divides 97^6-1, 7^2 divides 97^6-1
2914393 divides 97^971464-1, 2914393^2 divides 97^971464-1
2914393 divides 97^1942928-1, 2914393^2 divides 97^1942928-1
2914393 divides 97^2914392-1, 2914393^2 divides 97^2914392-1
--- Base 101 ---
5 divides 101^1-1, 5^2 divides 101^1-1
5 divides 101^2-1, 5^2 divides 101^2-1
5 divides 101^3-1, 5^2 divides 101^3-1
5 divides 101^4-1, 5^2 divides 101^4-1
1050139 divides 101^1050138-1, 1050139^2 divides 101^1050138-1
--- Base 103 ---
--- Base 107 ---
3 divides 107^2-1, 3^2 divides 107^2-1
5 divides 107^4-1, 5^2 divides 107^4-1
97 divides 107^96-1, 97^2 divides 107^96-1
613181 divides 107^122636-1, 613181^2 divides 107^122636-1
613181 divides 107^245272-1, 613181^2 divides 107^245272-1
613181 divides 107^367908-1, 613181^2 divides 107^367908-1
613181 divides 107^490544-1, 613181^2 divides 107^490544-1
613181 divides 107^613180-1, 613181^2 divides 107^613180-1
--- Base 109 ---
3 divides 109^1-1, 3^2 divides 109^1-1
3 divides 109^2-1, 3^2 divides 109^2-1
--- Base 113 ---
--- Base 127 ---
3 divides 127^1-1, 3^2 divides 127^1-1
3 divides 127^2-1, 3^2 divides 127^2-1
19 divides 127^18-1, 19^2 divides 127^18-1
907 divides 127^906-1, 907^2 divides 127^906-1
13778951 divides 127^6889475-1, 13778951^2 divides 127^6889475-1
13778951 divides 127^13778950-1, 13778951^2 divides 127^13778950-1
--- Base 131 ---
17 divides 131^16-1, 17^2 divides 131^16-1
--- Base 137 ---
29 divides 137^28-1, 29^2 divides 137^28-1
59 divides 137^29-1, 59^2 divides 137^29-1
59 divides 137^58-1, 59^2 divides 137^58-1
6733 divides 137^2244-1, 6733^2 divides 137^2244-1
6733 divides 137^4488-1, 6733^2 divides 137^4488-1
6733 divides 137^6732-1, 6733^2 divides 137^6732-1
--- Base 139 ---
--- Base 149 ---
5 divides 149^2-1, 5^2 divides 149^2-1
5 divides 149^4-1, 5^2 divides 149^4-1
29573 divides 149^29572-1, 29573^2 divides 149^29572-1
--- Base 151 ---
5 divides 151^1-1, 5^2 divides 151^1-1
5 divides 151^2-1, 5^2 divides 151^2-1
5 divides 151^3-1, 5^2 divides 151^3-1
5 divides 151^4-1, 5^2 divides 151^4-1
2251 divides 151^2250-1, 2251^2 divides 151^2250-1
14107 divides 151^14106-1, 14107^2 divides 151^14106-1
5288341 divides 151^2644170-1, 5288341^2 divides 151^2644170-1
5288341 divides 151^5288340-1, 5288341^2 divides 151^5288340-1
--- Base 157 ---
5 divides 157^4-1, 5^2 divides 157^4-1
122327 divides 157^3946-1, 122327^2 divides 157^3946-1
122327 divides 157^7892-1, 122327^2 divides 157^7892-1
122327 divides 157^11838-1, 122327^2 divides 157^11838-1
122327 divides 157^15784-1, 122327^2 divides 157^15784-1
122327 divides 157^19730-1, 122327^2 divides 157^19730-1
122327 divides 157^23676-1, 122327^2 divides 157^23676-1
122327 divides 157^27622-1, 122327^2 divides 157^27622-1
122327 divides 157^31568-1, 122327^2 divides 157^31568-1
122327 divides 157^35514-1, 122327^2 divides 157^35514-1
122327 divides 157^39460-1, 122327^2 divides 157^39460-1
122327 divides 157^43406-1, 122327^2 divides 157^43406-1
122327 divides 157^47352-1, 122327^2 divides 157^47352-1
122327 divides 157^51298-1, 122327^2 divides 157^51298-1
122327 divides 157^55244-1, 122327^2 divides 157^55244-1
122327 divides 157^59190-1, 122327^2 divides 157^59190-1
122327 divides 157^63136-1, 122327^2 divides 157^63136-1
122327 divides 157^67082-1, 122327^2 divides 157^67082-1
122327 divides 157^71028-1, 122327^2 divides 157^71028-1
122327 divides 157^74974-1, 122327^2 divides 157^74974-1
122327 divides 157^78920-1, 122327^2 divides 157^78920-1
122327 divides 157^82866-1, 122327^2 divides 157^82866-1
122327 divides 157^86812-1, 122327^2 divides 157^86812-1
122327 divides 157^90758-1, 122327^2 divides 157^90758-1
122327 divides 157^94704-1, 122327^2 divides 157^94704-1
122327 divides 157^98650-1, 122327^2 divides 157^98650-1
122327 divides 157^102596-1, 122327^2 divides 157^102596-1
122327 divides 157^106542-1, 122327^2 divides 157^106542-1
122327 divides 157^110488-1, 122327^2 divides 157^110488-1
122327 divides 157^114434-1, 122327^2 divides 157^114434-1
122327 divides 157^118380-1, 122327^2 divides 157^118380-1
122327 divides 157^122326-1, 122327^2 divides 157^122326-1
4242923 divides 157^4242922-1, 4242923^2 divides 157^4242922-1
--- Base 163 ---
3 divides 163^1-1, 3^2 divides 163^1-1
3 divides 163^2-1, 3^2 divides 163^2-1
3898031 divides 163^3898030-1, 3898031^2 divides 163^3898030-1
--- Base 167 ---
--- Base 173 ---
3079 divides 173^513-1, 3079^2 divides 173^513-1
3079 divides 173^1026-1, 3079^2 divides 173^1026-1
3079 divides 173^1539-1, 3079^2 divides 173^1539-1
3079 divides 173^2052-1, 3079^2 divides 173^2052-1
3079 divides 173^2565-1, 3079^2 divides 173^2565-1
3079 divides 173^3078-1, 3079^2 divides 173^3078-1
56087 divides 173^28043-1, 56087^2 divides 173^28043-1
56087 divides 173^56086-1, 56087^2 divides 173^56086-1
--- Base 179 ---
3 divides 179^2-1, 3^2 divides 179^2-1
17 divides 179^8-1, 17^2 divides 179^8-1
17 divides 179^16-1, 17^2 divides 179^16-1
35059 divides 179^17529-1, 35059^2 divides 179^17529-1
35059 divides 179^35058-1, 35059^2 divides 179^35058-1
126443 divides 179^63221-1, 126443^2 divides 179^63221-1
126443 divides 179^126442-1, 126443^2 divides 179^126442-1
--- Base 181 ---
3 divides 181^1-1, 3^2 divides 181^1-1
3 divides 181^2-1, 3^2 divides 181^2-1
101 divides 181^25-1, 101^2 divides 181^25-1
101 divides 181^50-1, 101^2 divides 181^50-1
101 divides 181^75-1, 101^2 divides 181^75-1
101 divides 181^100-1, 101^2 divides 181^100-1
--- Base 191 ---
13 divides 191^3-1, 13^2 divides 191^3-1
13 divides 191^6-1, 13^2 divides 191^6-1
13 divides 191^9-1, 13^2 divides 191^9-1
13 divides 191^12-1, 13^2 divides 191^12-1
379133 divides 191^379132-1, 379133^2 divides 191^379132-1
--- Base 193 ---
5 divides 193^4-1, 5^2 divides 193^4-1
4877 divides 193^4876-1, 4877^2 divides 193^4876-1
--- Base 197 ---
3 divides 197^2-1, 3^2 divides 197^2-1
7 divides 197^1-1, 7^2 divides 197^1-1
7 divides 197^2-1, 7^2 divides 197^2-1
7 divides 197^3-1, 7^2 divides 197^3-1
7 divides 197^4-1, 7^2 divides 197^4-1
7 divides 197^5-1, 7^2 divides 197^5-1
7 divides 197^6-1, 7^2 divides 197^6-1
653 divides 197^163-1, 653^2 divides 197^163-1
653 divides 197^326-1, 653^2 divides 197^326-1
653 divides 197^489-1, 653^2 divides 197^489-1
653 divides 197^652-1, 653^2 divides 197^652-1
6237773 divides 197^6237772-1, 6237773^2 divides 197^6237772-1
--- Base 199 ---
3 divides 199^1-1, 3^2 divides 199^1-1
3 divides 199^2-1, 3^2 divides 199^2-1
5 divides 199^2-1, 5^2 divides 199^2-1
5 divides 199^4-1, 5^2 divides 199^4-1
77263 divides 199^77262-1, 77263^2 divides 199^77262-1
1843757 divides 199^59476-1, 1843757^2 divides 199^59476-1
1843757 divides 199^118952-1, 1843757^2 divides 199^118952-1
1843757 divides 199^178428-1, 1843757^2 divides 199^178428-1
1843757 divides 199^237904-1, 1843757^2 divides 199^237904-1
1843757 divides 199^297380-1, 1843757^2 divides 199^297380-1
1843757 divides 199^356856-1, 1843757^2 divides 199^356856-1
1843757 divides 199^416332-1, 1843757^2 divides 199^416332-1
1843757 divides 199^475808-1, 1843757^2 divides 199^475808-1
1843757 divides 199^535284-1, 1843757^2 divides 199^535284-1
1843757 divides 199^594760-1, 1843757^2 divides 199^594760-1
1843757 divides 199^654236-1, 1843757^2 divides 199^654236-1
1843757 divides 199^713712-1, 1843757^2 divides 199^713712-1
1843757 divides 199^773188-1, 1843757^2 divides 199^773188-1
1843757 divides 199^832664-1, 1843757^2 divides 199^832664-1
1843757 divides 199^892140-1, 1843757^2 divides 199^892140-1
1843757 divides 199^951616-1, 1843757^2 divides 199^951616-1
1843757 divides 199^1011092-1, 1843757^2 divides 199^1011092-1
1843757 divides 199^1070568-1, 1843757^2 divides 199^1070568-1
1843757 divides 199^1130044-1, 1843757^2 divides 199^1130044-1
1843757 divides 199^1189520-1, 1843757^2 divides 199^1189520-1
1843757 divides 199^1248996-1, 1843757^2 divides 199^1248996-1
1843757 divides 199^1308472-1, 1843757^2 divides 199^1308472-1
1843757 divides 199^1367948-1, 1843757^2 divides 199^1367948-1
1843757 divides 199^1427424-1, 1843757^2 divides 199^1427424-1
1843757 divides 199^1486900-1, 1843757^2 divides 199^1486900-1
1843757 divides 199^1546376-1, 1843757^2 divides 199^1546376-1
1843757 divides 199^1605852-1, 1843757^2 divides 199^1605852-1
1843757 divides 199^1665328-1, 1843757^2 divides 199^1665328-1
1843757 divides 199^1724804-1, 1843757^2 divides 199^1724804-1
1843757 divides 199^1784280-1, 1843757^2 divides 199^1784280-1
1843757 divides 199^1843756-1, 1843757^2 divides 199^1843756-1
--- Base 211 ---
279311 divides 211^139655-1, 279311^2 divides 211^139655-1
279311 divides 211^279310-1, 279311^2 divides 211^279310-1
--- Base 223 ---
71 divides 223^35-1, 71^2 divides 223^35-1
71 divides 223^70-1, 71^2 divides 223^70-1
349 divides 223^58-1, 349^2 divides 223^58-1
349 divides 223^116-1, 349^2 divides 223^116-1
349 divides 223^174-1, 349^2 divides 223^174-1
349 divides 223^232-1, 349^2 divides 223^232-1
349 divides 223^290-1, 349^2 divides 223^290-1
349 divides 223^348-1, 349^2 divides 223^348-1
--- Base 227 ---
7 divides 227^6-1, 7^2 divides 227^6-1
40277 divides 227^40276-1, 40277^2 divides 227^40276-1
--- Base 229 ---
31 divides 229^30-1, 31^2 divides 229^30-1
• I find it interesting that you have not found one for base 47, (or 29 for that matter), both being members of the original Lucas series. Anyone have any ideas?
Message 6 of 18 , May 31, 2007
I find it interesting that you have not found one for base 47, (or 29
for that matter), both being members of the original Lucas series.

Anyone have any ideas?
• ... From: mistermac39 [mailto:mistermac39@hotmail.com] Sent: 31 May 2007 21:42 ... I only searched the first million primes from 3 in each base, so it s
Message 7 of 18 , May 31, 2007
-----Original Message-----
From: mistermac39 [mailto:mistermac39@...]
Sent: 31 May 2007 21:42

> I find it interesting that you have not found one for base 47, (or 29
> for that matter), both being members of the original Lucas series.
>
>Anyone have any ideas?

I only searched the first million primes from 3 in each base, so it's
possible that bases 29 and 47 have primes with similar characteristics.
• ... It s easy to find results from larger searches with Google. Here are some hits: http://www.fermatquotient.com/FermatQuotienten/FermQ_Sort
Message 8 of 18 , May 31, 2007
Kevin Acres wrote:
> I only searched the first million primes from 3 in each base,

It's easy to find results from larger searches with Google.
Here are some hits:
http://www.fermatquotient.com/FermatQuotienten/FermQ_Sort
http://www.loria.fr/~zimmerma/records/Fermat_quotients
http://www.math.niu.edu/~rusin/known-math/98/1093

--
Jens Kruse Andersen
• A little bit of pertinent information just arrived in my inbox: Wilfrid Keller and Jörg Richstein searched the bases b = 29, 47, 61 and found no example of
Message 9 of 18 , May 31, 2007
A little bit of pertinent information just arrived in my inbox:

Wilfrid Keller and Jörg Richstein searched the bases
b = 29, 47, 61
and found no example of
b^(p-1) = 1 mod p^2
for any prime for p < 10^11.

Kevin.

-----Original Message-----
From: Jens Kruse Andersen [mailto:jens.k.a@...]
Sent: 01 June 2007 12:33
Subject: [PrimeNumbers] Re: Thanks to all. Proposed binary Prime number test
fails.

Kevin Acres wrote:
> I only searched the first million primes from 3 in each base,

It's easy to find results from larger searches with Google.
Here are some hits:
http://www.fermatquotient.com/FermatQuotienten/FermQ_Sort
http://www.loria.fr/~zimmerma/records/Fermat_quotients
http://www.math.niu.edu/~rusin/known-math/98/1093
• ... Keller and Richstein are exhaustive for bases
Message 10 of 18 , May 31, 2007
--- In primenumbers@yahoogroups.com, "Jens Kruse Andersen"
<jens.k.a@...> wrote:

Keller and Richstein are exhaustive for bases < 1000 and exponents <
10^11.

http://www.mscs.dal.ca/~joerg/res/fq.html

OddPerfect.org has collected factors for some of these because Pace
Neilsen needed them in an approach to extending the minimum number of
distinct prime factors for an odd perfect number.

http://oddperfect.org/FermatQuotients.html
• ... Did you look at the first link I gave you: http://www.fermatquotient.com/FermatQuotienten/FermQ_Sort It includes those bases searched to 5.074*10^12 (with
Message 11 of 18 , Jun 1, 2007
Kevin Acres wrote:
> A little bit of pertinent information just arrived in my inbox:
>
> Wilfrid Keller and Jörg Richstein searched the bases
> b = 29, 47, 61
> and found no example of
> b^(p-1) = 1 mod p^2
> for any prime for p < 10^11.

Did you look at the first link I gave you:
http://www.fermatquotient.com/FermatQuotienten/FermQ_Sort
It includes those bases searched to 5.074*10^12 (with no odd solutions),
and much more.
It was updated 3 days ago and appears to be the current records.
http://www.fermatquotient.com/ says:
"http://www.fermatquotient.com/FermatQuotienten/News
Neues und Rekorde / News and records / Update 29.05.2007"

--
Jens Kruse Andersen
• This was meant to be sent to the group and I sent it to Jens by accident. If anyone else here has a PowerPC G5, I have a program that could search a range of
Message 12 of 18 , Jun 1, 2007
This was meant to be sent to the group and I sent it to Jens by
accident.

If anyone else here has a PowerPC G5, I have a program that could
search a range of about 1e12 in a day (for a single base).

--Mark
• I did indeed look through all of the interesting links that you sent. I m just wondering if I can get the time to work through the information and see if it
Message 13 of 18 , Jun 1, 2007
I did indeed look through all of the interesting links that you sent. I'm
just wondering if I can get the time to work through the information and see
if it holds true that p^2 always divides the minimal base^(p-1/x)-1 that p
does.

Kevin.

-----Original Message-----
From: Jens Kruse Andersen [mailto:jens.k.a@...]
Sent: 02 June 2007 01:12

[...]

Did you look at the first link I gave you:
http://www.fermatquotient.com/FermatQuotienten/FermQ_Sort
It includes those bases searched to 5.074*10^12 (with no odd solutions),
and much more.
It was updated 3 days ago and appears to be the current records.
http://www.fermatquotient.com/ says:
"http://www.fermatquotient.com/FermatQuotienten/News
Neues und Rekorde / News and records / Update 29.05.2007"
• ... I suspect it s provable, but I can t locate my copy of Hardy and Wright tonight to skim for inspiration. The minimal value is the column called order at
Message 14 of 18 , Jun 2, 2007
--- In primenumbers@yahoogroups.com, "Kevin Acres" <research@...> wrote:

> if it holds true that p^2 always divides the minimal
> base^(p-1/x)-1 that p does.

I suspect it's provable, but I can't locate my copy of Hardy and
Wright tonight to skim for inspiration.

The minimal value is the column called "order" at
http://oddperfect.org/FermatQuotients.html , so it was easy to verify
that p^2 divided the minimal value for all of those.

William
Poohbah of oddperfect.org
• ... Subscirbe! Phil () ASCII ribbon campaign () Hopeless ribbon campaign / against HTML mail / against gratuitous bloodshed [stolen with
Message 15 of 18 , Jun 3, 2007
--- Mark Rodenkirch <mgrogue@...> wrote:
> This was meant to be sent to the group and I sent it to Jens by
> accident.
>
> If anyone else here has a PowerPC G5, I have a program that could
> search a range of about 1e12 in a day (for a single base).

Subscirbe!

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________
Be a PS3 game guru.
Get your game face on with the latest PS3 news and previews at Yahoo! Games.
http://videogames.yahoo.com/platform?platform=120121
• ... YGM. --Mark [Non-text portions of this message have been removed]
Message 16 of 18 , Jun 3, 2007
On Jun 3, 2007, at 9:21 AM, Phil Carmody wrote:

> > This was meant to be sent to the group and I sent it to Jens by
> > accident.
> >
> > If anyone else here has a PowerPC G5, I have a program that could
> > search a range of about 1e12 in a day (for a single base).
>
> Subscirbe!

YGM.

--Mark

[Non-text portions of this message have been removed]
• ... Yes. Let d be the smallest value so that p divides b^d-1. First observe that if b^x-1 and b^y-1 and both divisible by p^2 (or any other number), then
Message 17 of 18 , Jun 5, 2007
--- In primenumbers@yahoogroups.com, "Kevin Acres" <research@...> wrote:

> just wondering ...
> if it holds true that p^2 always divides the
> minimal base^(p-1/x)-1 that p does.

Yes. Let d be the smallest value so that p divides b^d-1.

First observe that if b^x-1 and b^y-1 and both divisible by p^2 (or
any other number), then b^(gcd(x,y))-1 is also divisible by p^2 (or
any other number).

Second, observe that b^(pd)-1 is divisible by p^2. To see this,
express b^d as (ps+1), then expand (ps+1)^p with the binomial theorem.

Third, observe that every case of divisibility by p is of the form
b^(kd)-1, and every case of divisibility by p^2 is also a case of
divisiblity by p, so the minimal case of divisibility by p^2 must be
of the form b^(kd)-1.

Finally, if there is any k<p such that b^(kd)-1 is divisible by p^2,
then b^gcd(kd,pd) must also be divisible by p^2, but gcd(kd,pd)=d.

Therefore, in all cases of Vanishing Fermat Quotients, p^2 divides the
same primitive term that p divides.

William
Poohbah of OddPerfect.org

P.S. We still need a few large factors of Vanishing Fermat Quotients
at http://oddperfect.org/FermatQuotients.html
• Earlier, with reference to 29, and 47 the number 61 came up. It is a factor of the 15th Fibonacci number 610 Ring any bells?
Message 18 of 18 , Jun 14, 2007
Earlier, with reference to 29, and 47 the number 61 came up.

It is a factor of the 15th Fibonacci number 610

Ring any bells?
Your message has been successfully submitted and would be delivered to recipients shortly.