1
$\begingroup$

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}$ ($\,\phi\,$ is the Euler's totient function)?

Some examples are:

$p=2\;\rightarrow\;q=5,\,17,\,257,\,65537$

$p=7\;\rightarrow\;q=97,\,6597069766657$

$p=31\;\rightarrow\;q=7681,\,2013265921,\,2061584302081$

Many thanks.

Improve this question
$\endgroup$
7
  • 6
    $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu
    Commented Mar 18, 2020 at 5:20
  • 1
    $\begingroup$ 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). $\endgroup$
    – Mark Schultz-Wu
    Commented Mar 18, 2020 at 5:37
  • 1
    $\begingroup$ @Mark: Your "traditional heurstic" implies that there are infinitely many even prime numbers bigger than 5. $\endgroup$
    – user6976
    Commented Mar 18, 2020 at 5:57
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Mark Schultz-Wu
    Commented Mar 18, 2020 at 6:13
  • 2
    $\begingroup$ 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 $\endgroup$
    – Gerry Myerson
    Commented Mar 18, 2020 at 6:24

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .