I understand how RSA cryptosystem works; however, I am not sure how to apply it to answer these questions. Can someone explain please?
Let $N=3869$ and be equal to 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.
I understand and have worked out how to show the first part. However, I do not understand part 2. Can I get some help please?
This is a very nice question that feels like it should be obvious, but which isn't (or at least wasn't to me). I blame it on the phrasing "at least four".
When you figure out the nine messages, three of them are trivially $0, -1, 1$. When you have four, you have to have at least one nontrivial message. It turns out this is the key. [Originally I thought I would have to be clever and combine multiple of these messages together in some way. But you don't].
Call the message $M$. Then we consider messages $M^3 \equiv M \pmod {pq}$. Then we know that $$pq \mid M^3 - M = M(M+1)(M-1).$$ Since $M < pq$, we cannot have both $p,q$ dividing any of $M, M+1$ or $M-1$. (Since we're taking a nontrivial message, none of these are trivially $0$). Then taking $$\begin{align} &\gcd(M, N), \\ &\gcd(M+1, N), \\ &\gcd(M-1, N) \end{align}$$ will yield $p$ and $q$.