A240719 Numbers k such that 2^k == 1 (mod (k+1)^2).

1092, 3510

Offset: 1

Author

Felix Fröhlich, Apr 11 2014

Keywords

• hard
• more
• nonn
• bref

Comments

There are only two known terms.

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'.

Any further terms are greater than 1.2 * 10^17. - Charles R Greathouse IV, Apr 12 2014

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

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

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

Links

• J. Dobes and M. Kures, Search for Wieferich primes through the use of periodic binary strings, Serdica J. Computing, Volume 4, Number 3, 2010, 293-300.
• J. B. Dobson, A note on the two known Wieferich primes
• W. Johnson, On the nonvanishing of Fermat quotients (mod p), J. reine angew. Math., Issue 292 (Jan 1977), 196-200.
• L. C. Washington, On Fermat's last theorem, J. reine angew. Math., Issue 289 (Jan 1977), 115-117.

Crossrefs

Cf. A001220, A239875.

Programs

Mathematica

fQ[n_] := PowerMod[2, n, (n + 1)^2] == 1; Select[ Range@ 3600, fQ] (* Robert G. Wilson v, Jun 17 2015 *)

PARI

isok(n) = lift(Mod(2, (n+1)^2)^n) == 1; \\ Michel Marcus, Apr 12 2014

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)
test(1.2e17) \\ Test up to the current search bound for Wieferich primes; Charles R Greathouse IV, Apr 12 2014