5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Take $ n = p $, and note that $ \varphi(p^2) = p^2 - p $. $\endgroup$ – Starfall May 13 '16 at 16:41
  • $\begingroup$ 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. $\endgroup$ – Erick Wong May 21 '16 at 19:12
5
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.