Timeline for Are [Wieferich] primes the only solutions to the equation $2^{k-1} \equiv 1 \pmod{k^2}$?
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 27, 2023 at 9:48 | comment | added | user178594 | Please ask only one question per post. Therefore -1. | |
| Oct 15, 2021 at 18:04 | answer | added | Gottfried Helms | timeline score: 0 | |
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Sep 19, 2013 at 10:19 | answer | added | François G. Dorais | timeline score: 8 | |
| Sep 19, 2013 at 9:59 | comment | added | François G. Dorais | @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. | |
| Sep 19, 2013 at 9:56 | comment | added | Vesselin Dimitrov | @François: Why would the prime factors be Wieferich? In any case, as noted above, it appears that the Wieferich primes 1093 and 3511 (the only two known) are the only known integers $k > 1$ for which $k^2 \mid 2^{k-1}-1$. This does not say anything at all, however; for instance, there are expected to be more Carmichael numbers than there are primes, contrary to what the list at oeis.org/A002997 would appear to suggest (e.g., the smallest one being 561). | |
| Sep 19, 2013 at 9:43 | comment | added | François G. Dorais | Since these are precisely the base 2 pseudoprimes whose prime divisors are all Wieferich, there is no easy disproof: none of the very few known candidates work. | |
| Sep 19, 2013 at 9:25 | comment | added | Vesselin Dimitrov | @Gerry Myerson: You are right, I was careless here. If $k$ is Carmichael and $p$ a prime factor, then the condition $k \mid (p+1)^k-p-1$ certainly precludes $p^2 \mid k$. | |
| Sep 19, 2013 at 5:14 | comment | added | Gerry Myerson | @Vesselin, I believe Carmichael numbers are guaranteed to be squarefree. | |
| Sep 19, 2013 at 1:01 | comment | added | Vesselin Dimitrov | All I was trying to say was that the same heuristic which predicts that there should be about $\log\log{X}$ primes $p \leq X$ with $p^2 \mid 2^p - 2$, but only $O(1)$ (i.e., finitely many) with $p^3 \mid 2^p - 2$, suggests that your statement is false for infinitely many $k$, although it certainly has no known counterexamples. | |
| Sep 19, 2013 at 0:41 | comment | added | Kieren MacMillan | @DavidSpeyer: Thanks for the link. Now I just need to prove that no composites >3511 satisfy the congruence — for my purpose, I don’t need to find any primes >3511 which do, or prove that no more do. | |
| Sep 19, 2013 at 0:31 | history | edited | Kieren MacMillan | CC BY-SA 3.0 |
gave exact link to MSE cross-post
|
| Sep 19, 2013 at 0:28 | comment | added | Vesselin Dimitrov | As a matter of fact, even the sum of the inverses of (say, square-free, as you insist in the question) Carmichael numbers - those which are pseudoprime to any base prime to $k$ - would be expected to diverge. Just as well, there should be a subset $S$ of pair-wise coprime $k$'s with $\sum_S 1/k = +\infty$. For those, mod $k$ residues are to be considered as "independent events," as typical in heuristics about primes. Then note that, as $k$ runs through $S$, $(2^{k-1}-1)/k$ would be expected to take the residue $0$ with probability $1/k$. | |
| Sep 19, 2013 at 0:09 | comment | added | Vesselin Dimitrov | 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 . | |
| Sep 18, 2013 at 23:55 | comment | added | Vesselin Dimitrov | Shouldn't the sum of the inverses of the (square-free) $2$-pseudoprimes diverge to $+\infty$? If this is true (and I believe it is not known, but considered plausible), then on naive probabilistic (heuristic) grounds there are surely infinitely many such composite $k$: just note that the residue classes of $(2^{k-1} - 1)/k \mod{k}$ are expected to be distributed uniformly. (Also there should be finitely many positive integers $k$ for which the congruence holds mod $k^3$, but this is one of those questions about basic arithmetic whose answer we will probably never know.) | |
| Sep 18, 2013 at 23:40 | comment | added | Gerry Myerson | 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). | |
| Sep 18, 2013 at 23:23 | comment | added | David E Speyer | 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}". | |
| Sep 18, 2013 at 23:20 | comment | added | David E Speyer | @WillSawin Why? Suppose I compute $2^{k-1} \equiv 1 \mod k$ and $2^{k-1} \not \equiv 1 \mod k^2$. How do I know whether $k$ is prime? | |
| Sep 18, 2013 at 22:59 | comment | added | Will Sawin | Wouldn't an easy proof of that give an easy proof of PRIMES in P? | |
| Sep 18, 2013 at 22:29 | history | edited | Ricardo Andrade | CC BY-SA 3.0 |
replaced tag 'elementary'
|
| Sep 18, 2013 at 20:44 | comment | added | Aaron Meyerowitz | 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. | |
| Sep 18, 2013 at 20:13 | history | asked | Kieren MacMillan | CC BY-SA 3.0 |