|
%I #46 Jul 11 2021 16:03:04
%S 1092,3510
%N Numbers k such that 2^k == 1 (mod (k+1)^2).
%C There are only two known terms.
%C If p is in A001220, then p-1 is in the sequence. If k is in the sequence and k+1 is composite, then any prime factor of k+1 is in A001220 (see fifth comment for a proof). In that case, k+1 could be called a 'Wieferich pseudoprime'.
%C Any further terms are greater than 1.2 * 10^17. - _Charles R Greathouse IV_, Apr 12 2014
%C Both known terms have a periodic binary representation (i.e., 1092 = 010001000100, 3510 = 110110110110), so they are terms of A242139. Also, the ratio between those numbers and their divisor sums is 112/39 in both cases (see Dobson's website in the links and also A239875). Are those facts just coincidences? - _Felix Fröhlich_, Apr 15 2014
%C Proof of second part of second comment above: Let q be any odd prime factor of (k+1). Since 2 and q^2 are coprime, it follows from Euler's totient theorem (also known as Euler's theorem or Fermat-Euler theorem) that 2^(phi(q^2)) == 1 (mod q^2). Writing phi(q^2) = q^2 - q = q(q-1), one gets 2^(q(q-1)) == 1 (mod q^2). Taking the q-th root of both sides of the congruence yields 2^(q-1) == 1 (mod q^2). Q.E.D. - _Felix Fröhlich_, Jun 08 2015
%C If a(3) exists, it corresponds to A001220(3) - 1, i.e., a(3) + 1 must be prime. This can be shown the following way: Assume that a(3) + 1 is composite. Then the theorem from previous comment implies that a(3) + 1 is of the form 1093^x * 3511^y for some x, y >= 0 and x, y not both 0. If x or y is an integer k > 1, then p = 1093 or p = 3511 satisfies 2^(p-1) == 1 (mod p^(2k)). A quick check with PARI shows that neither 1093 nor 3511 satisfies this congruence for any k > 1. This leaves the case where x = y = 1, which can be excluded as well, since 3837523 is not in A001567. Q.E.D. - _Felix Fröhlich_, Jun 08 2015
%H J. Dobes and M. Kures, <a href="http://serdica-comp.math.bas.bg/index.php/serdicajcomputing/article/view/104">Search for Wieferich primes through the use of periodic binary strings</a>, Serdica J. Computing, Volume 4, Number 3, 2010, 293-300.
%H J. B. Dobson, <a href="http://library.uwinnipeg.ca/people/dobson/mathematics/Wieferich_primes.html">A note on the two known Wieferich primes</a>
%H W. Johnson, <a href="http://dx.doi.org/10.1515/crll.1977.292.196">On the nonvanishing of Fermat quotients (mod p)</a>, J. reine angew. Math., Issue 292 (Jan 1977), 196-200.
%H L. C. Washington, <a href="http://dx.doi.org/10.1515/crll.1977.289.115">On Fermat's last theorem</a>, J. reine angew. Math., Issue 289 (Jan 1977), 115-117.
%t fQ[n_] := PowerMod[2, n, (n + 1)^2] == 1; Select[ Range@ 3600, fQ] (* _Robert G. Wilson v_, Jun 17 2015 *)
%o (PARI) isok(n) = lift(Mod(2, (n+1)^2)^n) == 1; \\ _Michel Marcus_, Apr 12 2014
%o (PARI) test(lim)=my(t=1); for(i=0, log(lim)\log(1093), my(n=t); while(n<=lim, if(Mod(2,n^2)^(n-1)==1&&n>1, print(n-1)); n*=3511); t*=1093)
%o test(1.2e17) \\ Test up to the current search bound for Wieferich primes; _Charles R Greathouse IV_, Apr 12 2014
%Y Cf. A001220, A239875.
%K hard,more,nonn,bref
%O 1,1
%A _Felix Fröhlich_, Apr 11 2014
|
