I understand how RSA crytosystem works, however I am not sure how to apply it to answer these questions. Can someone explain please?
Let $N=3869$ and be the product of two distinct unknown odd prime numbers $p$ and $q$ such that $(p − 1)(q − 1)$ is not divisible by $3$. Show that there are exactly nine messages which are unchanged by RSA encryption using the public key $(N, 3)$.
Also explain how to find p and q if at least four of these messages are known.
If it is unchanged by the private key, then surely it is also unchanged by the public key (and vice versa). Thus, you must find the number of solutions to $m^3=m\pmod{N}$. This amounts to solving two different equations $m^3=m\pmod{p}$ and $m^3=m\pmod{q}$ and combining them using the Chinese remainder theorem. In each case, $m=0$ is a solution, and also the two solutions to $m^2=1$ (modulo the prime). Hence, there are nine solutions modulo $N$.
I haven't solved the next part, but it might be useful to note that having four solutions means, by the Pigeonhole principle, that there will be enough messages so that they will give at least two different values modulo both $p$ and $q$.