For $p|\varphi(n)$, we need that $n$ has a prime divisor $\equiv 1 \mod p$ or $p^2|n$. Let $c(n)$ be the highest order any $a$ coprime to $n$ has $\mod n$. By existence of primitive roots $\mod p^s$ for odd primes $p$, we get that $c(p^s)=\varphi(p^s)$. Also $c(2)=1 , c(4)=2 , c(2^{k+2}) = 2^k$ for $k \geq 1$. Additionally we have $c(ab)=\mathrm{lcm}(c(a),c(b))$ for all $a,b$. What we want is $c(n) \cdot p | \varphi(n)$. Let $n=\prod p_i^{v_i}$ be the prime decomposition of $n$. Then this is equivalent to $p \cdot \mathrm{lcm}_i (\varphi(p_i^{v_i})) | \prod \varphi(p_i^{v_i})$, so we must loose some factor $p$ in the $\mathrm{lcm}$, happening iff $p|\varphi(p_s^{v_s}) , \varphi(p_t^{v_t})$ for different $s,t$, equivalent to that there are two different primes $\equiv 1 \mod p$ dividing $n$ or at least one such prime together with $p^2|n$.

Pretty weird answer for me. I've got this result quite quick but then I had to check few cases to convice myself that I haven't omitted anything.

TomciO wrote: Pretty weird answer for me. I've got this result quite quick but then I had to check few cases to convice myself that I haven't omitted anything. Of course you have! If your solution is the same as ZetaX's, you didn't check the case $p=2$ which has extra solution $n=2^k$ for $k>2$. But it's not really important!

Sure, but it's a simple case and as you say it's not really important. Actually, I wasn't thinking about existence of more solutions, but on the contrary, I was looking for something which makes $n$ more specified (ofcourse I knew that this conditions are also sufficient but I tend to make stupid mistakes...).

Is $\varphi(n)$ Euler's totient function?

Yes. The thing which surprised me is unnatural lower bound for the length of the message (if I didn't write this I couldn't send the message). What is the sense of that? The value of text has nothing to do with his length.

You can trick it Well, I think it's against spammers or h4xx0rz or whatever.

I tricked it (by writing additional text and coloring it white).

For the case $p \geq 3$ the answer is all $n$ such that : • $n$ has two prime divisors $q_1,q_2$ such that $q_1,q_2 \equiv 1 \pmod p$ • $n$ has one prime divisor $q_1$ such that and $q_1 \equiv 1 \pmod p$ and $p^2 \mid n$ Proof : Consider the prime factorisation $n = q_1^{\alpha_1} \times q_2^{\alpha_2} \times \ldots \times q_k^{\alpha_k}$ and recall that $\phi(n) = (q_1-1) \times q_1^{\alpha_1} \times ( q_2 - 1) \times q_2^{\alpha_2} \times \ldots \times (q_k - 1) \times q_k^{\alpha_k}$ Now since $p \mid \phi{n}$ then $n$ must have a prime divisor such that $q_i \equiv 1 \pmod p$ (Or that $p^2 \mid n$, but we will only treat the former, since the latter is exactly the same essentially, follow along) , the trick is to consider that particular prime, i.e that since $q_i^{\alpha_i} \mid n$ then $q_i^{\alpha_i} \mid a^{\frac{\phi(n)}{p}} -1$. Now, it a known fact that there exists a primitive root modulo that prime. Hence write $\frac{\phi(n)}{p} =$ $\frac{\phi(\frac{n}{q_i^{\alpha_i}})\times \phi(q_i^{\alpha_i})}{p}$. If $p$ does not divide $\phi(\frac{n}{q_i^{\alpha_i}})$, then $p$ must divide $\phi(q_i^{\alpha_i}$, but since the primitive root has order $\phi(q_i^{\alpha_i}$, this is a contradiction. (Basically, $\phi(q_i^{\alpha_i}$ looses that $p$ divisor, and it must get it back to achieve order, and it can only get it from $\phi(\frac{n}{q_i^{\alpha_i}})$ which is not even divisible by $p$) Hence $p \mid \phi(\frac{n}{q_i^{\alpha_i}})$, thus $n$ has either another prime divisor $q_j \equiv 1 \pmod p$ (So we can have $p \mid q_j - 1$ or that $p^2 \mid n$ (So we can have $p$ is the factorisation of $\phi(n)$). For $p = 2$, we must have : • $n$ is divisible by two distinct odd primes. • $n$ is divisible by an odd prime and $4 \mid n$ • $n = 2^k$ for $k \geq 3$ Proof : Recall that $\phi(n)$ is always even for $n \geq 3$, so if $n$ is divisible by two odd primes, you can repeat essentially the same proof as above (Stated with less rigour, when you loose that factor of $2$ by division, the other $\phi$ will give it back) If it is only only divisible by one prime, then again you can repeat the same proof as above, and see that you must have $4 \mid n$ (and again, that $4$ is to get the factor of $2$ back) Now suppose that $n = 2^k$, we check manually that $n = 2,4$ are not solutions. For $n = 2^k$ with $k \geq 3$, we must show that $2^k \mid a^{\frac{\phi(2^k)}{2}} - 1$ holds, i.e that $2^k \mid a^{2^{k-2}} - 1$ which is true since $a^{2^{k-2}} - 1 = (a^{2^{k-1}} + 1)\times(a^{2^{k-1}} + 1)\ldots(a + 1)\times(a - 1)$ : There are $k - 1$ even factors in this expression ($\gcd(a,n) = \gcd(a,2^k) = 1$, thus $a$ must be odd) , and one of $(a - 1)$ or $(a + 1)$ must be divisible by $4$, hence this expression is divisible by $2^k$, as wanted.