# Conjecture about odd primes

For each odd prime $p$ there exist $n\in\mathbb{N}$ such that $p\equiv n^2 \text{ (mod }\varphi(n^2))$, where $\varphi$ is Euler's totient function.

I'm developing my Forth based computational system Zet to be used for testing conjectures and it seems that it generate conjectures as well...

What I have tried is to test the modular condition for squares of all integers less than $n$. All odd primes less than $n$ are represented then. It's not so that all odd number is represented - which seems to be the case if dropping the squaring: $p\equiv n \text{ (mod }\varphi(n))$ - instead the most of the numbers represented are primes.

• Take $n = p$, and note that $\varphi(p^2) = p^2 - p$. – Starfall May 13 '16 at 16:41
• It's also true for $n=1$. This is a trivial solution but I imagine you need to be very precise with computational systems, and $n=1$ precisely satisfies the statement as written. – Erick Wong May 21 '16 at 19:12

Your conjecture is (trivially) true, because we have $\varphi(p^2) = p^2 - p$ for $p$ prime, so that we have $p \equiv p^2 \pmod{\varphi(p^2)}$. Thus, we may simply take $n = p$ for any prime number.