Modular Arithmetic Congruence Question If $c$ is odd and $cy$ $≡$ $4$ mod $n$, then $c$ is coprime to $n$.
Then it follows that $cy-4 = na$, so $cy-na = 4$. Then by Bezout's lemma, there exists integers $d$ and $w$ where $d=y$ and $e=-a$ such that $cd+na=4$, so the hcf($c,n$) = $4$, but this contradicts the fact that $c$ is odd. Contradiction, so $c$ and $n$ are coprime.
I feel like it isn't correct to apply Bezout's lemma like this. Help!
 A: Alternative approach:
Given that :

*

*$cy \equiv 4 \pmod{n}$


*$c$ is odd.
To prove: $c$ is co-prime to $n$.
Without loss of generality, $c$ is not equal to either $(1)$ or $(-1)$. 
For example, if $c = 1$, you could take $y = 13, n = 9.$ 
If $c = -1$, you could take $y = -13, n = 17.$ 
In both cases, you would have that $c,n$ are relatively prime.
From the premise, you know that $n$ divides $(cy - 4)$.
Suppose that $c$ is not co-prime to $n$.
Then, there exists some prime number $p$ such that $p$ divides $n$ and $p$ divides $c$.
Further, since $c$ is odd, you know that the prime number $p$ must be odd.
Since $n$ divides $(cy - 4)$, there exists some integer $a$ such that $an = cy - 4.$  Further, since $c$ is assumed to not equal $1$ or $-1$, and $c$ is odd, you know that $(cy)$ is not equal to $(4)$.
Therefore, $cy - 4$ is not equal to $(0)$.  Therefore, $a$ is not equal to $(0)$.
So, you have that
$cy - an = 4$ and that $p$, an odd prime, divides both $n$ and $c$.  Therefore, the odd prime $p$ divides $4$.  This yields a contradiction.
Since the contradiction was explicitly caused by the assumption that there exists some prime $p$ such that $p$ is a factor of both $c$ and $n$, this assumption must be false.
Therefore, $c$ and $n$ must be coprime.
