15
$\begingroup$

While studying a certain Diophantine equation in the squarefree integer $k \ge 2$, I believe I have proven the necessary restriction

$$2^{k-1} \equiv 1\!\!\pmod{k^2}. \qquad(\star)$$

Based on what I read about Wieferich primes on Wikipedia (http://en.wikipedia.org/wiki/Wieferich_prime), if $k$ is a prime, it must be a Wieferich prime. So far, so good.

However, I haven’t found anything — on Wikipedia or elsewhere — that proves there are no composite solutions to the congruence ($\star$). Is that statement true? If so, what’s an easy proof? If not, what's an easy disproof?

Many thanks,
Kieren.

n.b. I asked this same question on MSE earlier today (https://math.stackexchange.com/questions/497810/are-wieferich-primes-the-only-solutions-to-2n-1-equiv-1-pmodn2), but now realize it might be more suitable here due to its possible complexity. Apologies if that's inappropriate.

$\endgroup$
  • 3
    $\begingroup$ Your condition certainly requires $2^{k-1} \equiv 1\!\!\pmod{k}$ which makes $k$ a prime or a $2$-pseuedoprime. You can find the first few and a link to a longer list at oeis.org/A001567. At least none of those listed has the property. $\endgroup$ – Aaron Meyerowitz Sep 18 '13 at 20:44
  • 2
    $\begingroup$ According to oeis.org/A001567 "There are only two known numbers n such that n^2 divides 2^(n-1) - 1, A001220(n) = {1093, 3511}". $\endgroup$ – David E Speyer Sep 18 '13 at 23:23
  • 1
    $\begingroup$ Not quite what you want, but there are composite $k$ such that $2^{\phi(k)}\equiv1\pmod{k^2}$, where $\phi$ is the Euler totient function. $3279=3\times1093$ is such a number. A reference is Agoh, Dilcher, and Skula, Fermat quotients for composite moduli, J Number Theory 66 (1997) 29-50, MR1467188 (98h:11002). $\endgroup$ – Gerry Myerson Sep 18 '13 at 23:40
  • 1
    $\begingroup$ Indeed, you can find in this paper by Pomerance a precise conjectural distribution of the pseudoprimes; in particular, there should be more $2$-pseudoprimes than there are primes, and the heuristic applies to answer your question negatively: dei.unipd.it/~geppo/AA/DOCS/pseudoprimes.pdf . $\endgroup$ – Vesselin Dimitrov Sep 19 '13 at 0:09
  • 1
    $\begingroup$ @Vesselin: The order of $2$ mod $p^2$ is either the order of $2$ mod $p$ (when $p$ is Wieferich) or $p$ times that. If $p \mid k$ and the order of $2$ mod $k^2$ divides $k-1$ then the second case is impossible. $\endgroup$ – François G. Dorais Sep 19 '13 at 9:59
7
$\begingroup$

This was a comment but it's actually a partial answer...

First, note that for an odd prime $p$ the order of $2$ mod $p^2$ is either equal to the order of $2$ mod $p$ or exactly $p$ times that. The first case happens if and only if $p$ is a Wieferich prime. Now if $2^{k-1} \equiv 1 \pmod{k^2}$ holds then the order of $2$ mod $p^2$ must divide $k-1$ for every prime $p \mid k$. Since $p$ does not divide $k-1$, it must be the case that all prime divisors of $k$ are Wieferich. Since none of the products of known Wieferich primes work, there is no "easy disproof" of the claim. Given the current state of affairs, there are no composite numbers $k \leq 6.7\times10^{18}$ such that $2^{k-1} \equiv 1 \pmod{k^2}$. The reasoning above actually gives a characterization of the squarefree numbers $k$ that satisfy $2^{k-1} \equiv 1 \pmod{k^2}$. These are the squarefree base $2$ pseudoprimes whose prime factors are all Wieferich.

On the positive side, Carl Pomerance suggested to look at a paper of his with Zachary Franco, On a conjecture of Crandall concerning the $qx+1$ problem. There, they consider Wieferich numbers which are characterized by $\operatorname{gcd}((2^{\ell(k)}-1)/k,k) \gt 1$, where $\ell(k)$ is the order of $2$ modulo $k$. This is much weaker than your condition $(\star)$ but Pomerance and Franco show that Wieferich nubers have asymptotic density $1$ in the odd numbers. While this is by no means affirmative, it does suggest that there might be composite solutions to the congruence $2^k \equiv 1 \pmod{k^2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.