[proofplan] We translate the congruence $ca \equiv cb \pmod{n}$ into the divisibility statement $n \mid c(a-b)$. Since $c$ is relatively prime to $n$, Bezout's identity gives integers $u$ and $v$ with $uc+vn=1$. Multiplying this identity by $a-b$ expresses $a-b$ as a sum of two integers each divisible by $n$, so $n \mid a-b$, which is exactly $a \equiv b \pmod{n}$. [/proofplan] [step:Rewrite the congruence as a divisibility statement] By the definition of congruence modulo $n$, the hypothesis \begin{align*} ca \equiv cb \pmod{n} \end{align*} means that $n$ divides $ca-cb$. Since \begin{align*} ca-cb = c(a-b), \end{align*} there exists an integer $k \in \mathbb{Z}$ such that \begin{align*} c(a-b)=kn. \end{align*} [guided] The goal is to prove $a \equiv b \pmod{n}$, and by definition this means proving that $n$ divides $a-b$. The given congruence only tells us something about $c(a-b)$, so the first task is to write that information in divisibility form. By the definition of congruence modulo $n$, the hypothesis \begin{align*} ca \equiv cb \pmod{n} \end{align*} means precisely that $n$ divides the difference $ca-cb$. Factoring the difference gives \begin{align*} ca-cb = c(a-b). \end{align*} Therefore $n \mid c(a-b)$. Equivalently, there is an integer $k \in \mathbb{Z}$ such that \begin{align*} c(a-b)=kn. \end{align*} This is the exact point where the problem becomes a cancellation problem: we know $n$ divides a product involving $c$, and the coprimality hypothesis will allow us to remove the factor $c$. [/guided] [/step] [step:Use coprimality to build a Bezout identity] Since $\gcd(c,n)=1$, Bezout's identity gives integers $u,v \in \mathbb{Z}$ such that \begin{align*} uc+vn=1. \end{align*} Here we use Bezout's identity as the standard characterization of relatively prime integers (citing a result not yet in the wiki: Bezout's identity). [/step] [step:Multiply the Bezout identity by $a-b$ and isolate divisibility by $n$] Multiplying \begin{align*} uc+vn=1 \end{align*} by $a-b$ gives \begin{align*} a-b = uc(a-b)+vn(a-b). \end{align*} From the previous step, $c(a-b)=kn$, so \begin{align*} uc(a-b)=ukn. \end{align*} Also, \begin{align*} vn(a-b)=v(a-b)n. \end{align*} Since $u,k,v,a-b \in \mathbb{Z}$, both $ukn$ and $v(a-b)n$ are divisible by $n$. Hence their sum is divisible by $n$, so \begin{align*} n \mid (a-b). \end{align*} [/step] [step:Translate divisibility back into the desired congruence] By the definition of congruence modulo $n$, the divisibility statement \begin{align*} n \mid (a-b) \end{align*} is equivalent to \begin{align*} a \equiv b \pmod{n}. \end{align*} This proves the cancellation criterion. [/step]