# The congruence $n\equiv\varphi(n) \pmod p$

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.

• 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. – Geoff Robinson Aug 17 '16 at 18:28
• 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).$ – Geoff Robinson Aug 17 '16 at 18:36
• I have edited my question – Werner Aumayr Aug 18 '16 at 6:42
• $n-\varphi(n)$ in general has additional different prime Divisors than $n$ – Werner Aumayr Aug 18 '16 at 6:45
• 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. – Geoff Robinson Aug 18 '16 at 8:36