Has the congruence $n\equiv\varphi(n) \pmod p$, with $p$ being an odd prime not dividing $n$, been examined before?

Because it is easy to find solutions for $n$ with few primes in its decomposition (e.g., $n=14007$, $p=5$), a classification of solutions with respect to $\omega(n)$ would be interesting.

  • $\begingroup$ I suppose that you are really thinking about primes which do not divide $n$, since the congruence holds whenever $p^{2}$ divides $n$ with $p$ prime. $\endgroup$ – Geoff Robinson Aug 17 '16 at 18:28
  • 3
    $\begingroup$ Actually, it is in some sense routine to calculate the primes $p$ which divide $n - \phi(n)$: Let $n = p_{1}^{m_{1}} \ldots p_{r}^{m_{r}}.$ Then the prime divisors of $n - \phi(n)$ are the primes $p_{i}$ with $m_{i}>1$, together with the primes $p$ which divide $\prod_{i=1}^{r} p_{i} - \prod_{i=1}^{r}(p_{i}-1).$ $\endgroup$ – Geoff Robinson Aug 17 '16 at 18:36
  • $\begingroup$ I have edited my question $\endgroup$ – Werner Aumayr Aug 18 '16 at 6:42
  • $\begingroup$ $n-\varphi(n)$ in general has additional different prime Divisors than $n$ $\endgroup$ – Werner Aumayr Aug 18 '16 at 6:45
  • $\begingroup$ Yes indeed, as my second comment makes clear. With the notation as in that comment, you are looking at the prime divisors of $\sum_{ \phi \neq J \subseteq I} (-1)^{|J|} \prod_{ i \in I \backslash J} p_{i}$, where $I = \{1,2,\ldots ,r\}$, together with the primes which divide $n$ to thhe second or higher power. $\endgroup$ – Geoff Robinson Aug 18 '16 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.