# Proving $n\equiv p [k] \Longleftrightarrow \gcd(p,k)=\gcd(n,k)$

I'm wondering if this statement is correct :

$n\equiv p [k] \Longleftrightarrow \gcd(p,k)=\gcd(n,k)$.

If it is:

• What are the conditions that must be assured before using it?
• How can I prove that statement?
-

Write $a=\gcd(p,k)$, $p=ap'$, and $k=ak'$ for some $p',k'$ with $\gcd(p',k')=1$.
If $n\equiv p\pmod{k}$ then $k|(n-p)$. The latter is equivalent to $ak'|(n-ap')$. Hence $a|n$ and thus $\gcd(p,k)=a|\gcd(n,k)$. A symmetric argument shows $\gcd(n,k)|\gcd(p,k)$ so they are equal.
The other direction is not true. A counterexample is $k=3, n=1, p=2$.