Recover plaintext in passive attack of RSA of coprime public key

Question

I have a situation in RSA like this.

Charles sends same message $m$ to Alice and Bob encrypted with $e_A$ and $e_B$ respectively. It happens that he they are under same modulus $n$ and $gcd(e_A, e_B)=1$. Now Eve intercepts two messages $c_A$ and $c_B$. The claim is that Eve can easily get $m$ in this situation.

My thought on this case is follows:

1. With $e_A$ and $e_B$ coprime, Eve can use the extended Euclidean algorithm to get solution to $1=a_1e_A+a_2e_B$. She then calculate $(c_A)^{a_1}(c_B)^{a_2} \bmod n = m \bmod n $

2. Now the problem is that one of $a_1$ and $a_2$ is actually negative (let's assume $a_1$). So the above $(c_A)^{a_1}$ involves calculation of an inverse modulo $n$. Yet I think $c_A$ is not necessarily be invertible.

3. An concrete example I can think of: $p=5$, $q=7$, $n=35$, $\phi(n)=24$, $e=11$, $m=21$, in this case, $c_A = 21$, not invetible.

I think somehow Eve must be able to recover the message. But I simply got stuck in above analysis.

Am I missing something? Please point out! Thanks so much!

Answer 1

Hint: if $c_A$ is not invertible, what does that say about $gcd(c_A, n)$? How can you exploit that to obtain $m$ in another way?