5
$\begingroup$

I would like to search for primes of the form $$\varphi(n)^n+n$$ where $\ \varphi(n)\ $ denotes the totient function.

The problem is that neither pfgw nor factordb seems to support the totient-function.

Is there some trick allowing to determine the totient-function with some other functions that are supported by pfgw ?

With PARI/GP, I calculated the positive integers $n$, such that the above expression is prime. These are $\ 1,2,3,187\ $ and no other below $\ 3\ 000\ $

$\endgroup$
9
  • 4
    $\begingroup$ Clearly $n$ must be square free, hence is the product of distinct primes. But if $n=\prod p_i$ then $\varphi(n)=\prod (p_i-1)$. $\endgroup$
    – lulu
    Commented May 31, 2019 at 11:08
  • $\begingroup$ @lulu Nice observation! Unfortunately, pfgw does not support this either. $\endgroup$
    – Peter
    Commented May 31, 2019 at 11:12
  • $\begingroup$ Well, your numbers are so small that you can code that explicitly. Granted, this gets a lot harder if it is difficult to factor $n$ but for small $n$ this is not difficult. $\endgroup$
    – lulu
    Commented May 31, 2019 at 11:17
  • $\begingroup$ @lulu pfgw and factordb would however be much faster in primality testing. That is the reason, I ask. $\endgroup$
    – Peter
    Commented May 31, 2019 at 11:25
  • 1
    $\begingroup$ For what it's worth, Wolfram Alpha can check up to 200: Select[Range[200], PrimeQ[EulerPhi[#]^# + #] &] $\endgroup$
    – Robert Soupe
    Commented May 31, 2019 at 16:28

1 Answer 1

Reset to default
3
$\begingroup$

The totient function of an integer $n$ with prime factorisation $\prod \limits_{k=1}^r p_k^{\alpha_k}$ is given by $\varphi(n) = \prod \limits_{k=1}^r p_k^{\alpha_k-1}(p_k-1)$. This allows you to determine the totient based off a prime factorisation, and furthermore also tells you that $n$ cannot have a square factor since if $p^2$ divides $n$ then $p$ divides $\varphi(n)$, and so we now have $\varphi(n) = \prod \limits_{k=1}^r (p_k-1)$ where $n$ is a product of distinct primes.

$\endgroup$
4
  • $\begingroup$ As far as I know, this approach cannot be applied in pfgw. $\endgroup$
    – Peter
    Commented May 31, 2019 at 11:12
  • $\begingroup$ why the obsession with PFGW ? $\endgroup$
    – user645636
    Commented May 31, 2019 at 23:21
  • $\begingroup$ @RoddyMacPhee Seems you don't read the comments, when it comes to huge numbers, pfgw is far superior in primality testing compared to pari/gp. And I am particular interested in huge primes. I do not know what you want to show with Fermat's little theorem in context with this question, but lulu's comment ($n$ must be squarefree) and that $n$ must obviously be odd (expcept $n=2$) is already quite restricting. $\endgroup$
    – Peter
    Commented Jun 1, 2019 at 11:11
  • $\begingroup$ n=4 mod 20, forces phi(n) to be 0 mod 5 or bust. 6 mod 20 forces not 2 or 3 mod 5 phi(n). etc. $\endgroup$
    – user645636
    Commented Jun 1, 2019 at 11:29

You must log in to answer this question.

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