17
$\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.

Improve this question
$\endgroup$
16
  • 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
    Commented Sep 18, 2013 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
    Commented Sep 18, 2013 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
    Commented Sep 18, 2013 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
    Commented Sep 19, 2013 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
    Commented Sep 19, 2013 at 9:59

2 Answers 2

Reset to default
8
$\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}$.

Improve this answer
$\endgroup$
1
0
$\begingroup$

In an older essay I looked at the "composites"-generalization of Wieferich- and generalized Wieferich-primes. I found such solutions, and documented that cases in a couple of tables. Here is a screenshot of the table with "Wieferich-composites" (to base $2$:

(...) enter image description here ...

(from "High fermat- and Euler-quotients" . Note: the essay is an amateur's work, not a true research paper)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .