The Instant Google type-in anticipator for pseudop... proposed pseudopseudohypoparathyroidism.
On Tue, Apr 30, 2013 at 5:06 PM, Bill Gosper <billgosper@gmail.com>wrote:
Wow. Nice. It appears that the base 2 6.7x10^15 search https://cs.uwaterloo.ca/journals/JIS/VOL14/Klyve/klyve3.html omitted pseudoprimes. A moronic Mma search thru 5.7G is so far fruitless. Has no one tried this before? --rwg
rcs>If we vary the base, we can arrange for Wieferich pseudoprimes: Start
with the known base 2 psp 341: 2^340 = 1 (mod 341) while 341 = 11*31 is composite. But 2^340 = 34783 (mod 341^2), so the "tens digit" is 102, [34782/341]. We muck around with the tens digit: (2+341K)^340 (mod 341^2) = 2^340 + 340 * 2^339 * 341K + stuff * 341^2. The coefficient of 341K is effectively -1/2, so Set K=204 to zero out the tens digit from 2^340. 69566^340 = 1 (mod 341^2) and 69566^341 = 69566 (mod 341^2). Rich ----- Quoting Bill Gosper <billgosper@gmail.com>:
Is it obvious that if n∈N and 2==Mod[2^n,n^2] then n is (a Wieferich) prime? Why don't we just call A001220 Wieferich numbers? --rwg
--
FredH>
Any prime divisor of a "Wieferich pseudoprime" (i.e., a composite n
such that 2^n == 2 (mod n^2)) must itself be a Wieferich prime. A proof can be found here (of all places):
http://forums.xkcd.com/viewtopic.php?t=23397&p=699486
Julian reads the strip, but not the forums, and unaware of this item, privately sent a stronger thm:
"I don't know whether the Wieferich property implies primality, but it does imply that all prime factors of the number are Wieferich primes. If 2^n=2 mod n^2, p|n is prime, and e is the order of 2 mod p^2 (p=2 doesn't work, since then 4 would divide n^2 and 2^n but not 2), then we must have e|n-1, so p does not divide e. Then e|p-1 and 2^p=2 mod p^2. Similarly, if n is divisible by p^k, we must have that 2^p=2 mod p^2k. Since this fails for known Wieferich primes and k>1, and 1093*3511 does not work, any composite example must be >10^20. Similar constraints hold for other bases–if a^n=a mod n^2 and p^k|n, then a^p=a mod p^2k." Julian Testing this on Rich's example, In[162]:= PowerMod[69566, 1, 121] Out[162]= 112 In[167]:= PowerMod[112, 11, 121] Out[167]= 112 In[163]:= PowerMod[69566, 1, 31^2] Out[163]= 374 In[165]:= PowerMod[374, 31, 31^2] Out[165]= 374 So 11 is a Wieferich prime base 112 and 37 is a Wieferich prime base 374. So it should be easy to collect lots of Wieferich primes to weird bases. Can these somehow point to some huge Wieferich pseudoprime base 2, yielding some new Wieferich prime, probably not the next? --rwg rwg>
Is it obvious that if n∈N and 2==Mod[2^n,n^2] then n is (a Wieferich)
prime? Why don't we just call A001220 Wieferich numbers? --rwg
The term "Wieferich number" has been used for n such that 2^phi(n) == 1 (mod n^2); see A077816.
OK, I guess we're stuck with Wieferich [pseudo]prime.
Is {2}, the feasible Fermat exponent(s), in the OEIS? Perhaps there should be an entry for {}, the supposed infinitude of false positives from http://en.wikipedia.org/wiki/Baillie-PSW_primality_test , for a single example of which there stands a $620 cash bounty.