I am currently studying for an exam and attempting the following past exam question:
Let $N$ be the product of two distinct odd prime numbers $p$ and $q$ which are both congruent to $3\pmod 4$. Suppose further that $(p-1)(q-1)$ is not divisible by $3$. Show that there do not exist two distinct messages which are interchanged by RSA encryption using the public key $(N, 3)$. (Hint: You may assume that if $r$ is a prime number congruent to $3\pmod 4$ then $-1$ is not a square in $\mathbb{Z}_r$.)
Unfortunately, I am unable to tackle it really or see the direction I am aiming for. In particular, what would the relevance of $p,q$ being congruent to $3\pmod4$ be? As far as I am aware this implies something about them being prime but as we were already given previously that they are both distinct and prime, what was the purpose of this congruence?
Also, when asked to show that no two distinct messages can be interchanged using the encryption, I suppose I am trying to show there exist no solutions $$m^3 = n^3, m\neq n. $$
However, I don't see how to make use of the hint. Just trialling things:
Say we work in $\pmod p$ $$m^3 \equiv n^3 \implies m^3-n^3 \equiv 0. $$
I think I should factorise this and find a term with squares involved and then potentially make use of the hint but I'm not sure really...
Any points in the right direction are greatly appreciated.
UPDATE:
Following on new advice in the comments I have attempted the following;
Since the messages are interchanged this actually means that $E(m)=n$ and $E(n)=m$.
So lets say we are working in $\pmod p$. We then have $$m^3 \equiv n , n^3 \equiv m.$$
My approach would be to treat these as simultaneous equations.
$m^3-n=0$
$n^3-m=0$
Multiplying the second equation by $m^2$ and adding the two equations together we find $$ n(m^2-1)=0.$$ Of course the possible solutions are: $n=0, m^2-1=0.$ We see that $n=0$ cannot be a solution as that would imply $m = 0$ from our equation $n^3-m=0$. So, let's say our solution is $m^2-1=0$, this give us the possible values $m=1,-1.$ Using the hint we can exclude $m=-1$ as a possible solution, which then leaves us with $m=1$.
However, from our equation $m^3-n=0$ this would imply $1-n=0 \implies n=1$ but as $m \neq n$ this cannot be true.
Hence there are NO solutions in $\pmod p$, the same argument can be used for $\pmod q$ thus $0\times0=0$ so there are no solutions in $\pmod N$ implying that there are no two distinct messages that could be interchanged by this system.