Timeline for Given a prime $\,p\ne3$, is it always possible to find another prime q such that $\,\phi(q)=\phi(p\cdot2^{2n+1})\,$ for some $n\in\mathbb{N}$?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 18, 2020 at 19:13 | vote | accept | Augusto Santi | ||
| Mar 18, 2020 at 6:37 | comment | added | Wlod AA | Wacław Sierpiński? (Is this a good association?) | |
| Mar 18, 2020 at 6:24 | comment | added | Gerry Myerson | There are infinitely many $k$ such that $2^mk+1$ is composite for all $m$. Whether any such $k$ is $p-1$, I don't know. See en.wikipedia.org/wiki/Seventeen_or_Bust | |
| Mar 18, 2020 at 6:13 | comment | added | Mark Schultz-Wu | @MarkSapir I mostly included the computation because it would have been interesting if the sum converged, as the only thing holding back the answer from being "Trivially yes due to Dirichlet's theorem, and there are in fact infinitely many such $q$" is the sparsity of $A$ within $\{(p-1)n+1\mid n\in\mathbb{N}\}$. Even if $A$ was sparse enough such that $\sum_{a\in A}1/\ln(a)$ converged (and the heuristic was 100% true, which as you mention is spurious), this wouldn't rule out there being finitely many (or of note, 1) primes in $A$. | |
| Mar 18, 2020 at 5:57 | comment | added | user6976 | @Mark: Your "traditional heurstic" implies that there are infinitely many even prime numbers bigger than 5. | |
| Mar 18, 2020 at 5:42 | history | edited | Augusto Santi | CC BY-SA 4.0 |
added 31 characters in body
|
| Mar 18, 2020 at 5:37 | comment | added | Mark Schultz-Wu | It's worth mentioning that the traditional heuristic of stating that a set $A\subseteq\mathbb{N}$ contains infinitely many primes if $\sum_{a\in A} \Pr[a\text{ is prime}] = \sum_{a\in A} 1/\ln(a)$ diverges seems to (heuristically) suggest that there should be infinitely many such $q$, as $\ln(a) = \Theta(n)$ so this sum should behave approximately like the harmonic sum (and diverge). | |
| Mar 18, 2020 at 5:30 | comment | added | Mark Schultz-Wu | This seems related to this question | |
| Mar 18, 2020 at 5:20 | comment | added | Mark Schultz-Wu | Elementary properties of $\phi$ allows one to rewrite the equality as $(q-1) = (p-1)2^{2n}$, or $q = (p-1)2^{2n} + 1$. One might as well define $A = \{(p - 1)2^{2n} + 1\mid n\in\mathbb{N}\}$, and ask if this set always contains a prime. If we had $n$ instead of $2^{2n}$ it would follow from Dirichlet's theorem on primes in arithmetic progressions (and there would be infinitely many such primes $q$). Instead you look at a sparse subset of $A$, but ask only if it has a single prime in it. | |
| Mar 18, 2020 at 5:12 | history | edited | Augusto Santi | CC BY-SA 4.0 |
added 33 characters in body
|
| Mar 18, 2020 at 4:36 | history | asked | Augusto Santi | CC BY-SA 4.0 |