If x divides ab and x is coprime to a, then x divides b

Dependencies:

1. Coprime
2. GCD is the smallest Linear Combination

If $x \mid ab$ and $x$ is coprime to $a$, then $x \mid b$.

Proof by contradiction

Assume $x \not\mid b$.

\begin{align} &\Rightarrow \gcd(x, a) = 1 \\ &\Rightarrow \exists r \exists s \textrm{ such that } xr + as = 1 \\ &\Rightarrow xrb + asb = b = x(rb) + s(ab) \\ &\Rightarrow x \mid b \Rightarrow \bot \end{align}

This is a contradiction, which means $x \mid b$.

Dependency for:

1. Multiplication permutes Zn*
2. Order of elements in cyclic group

Info:

• Depth: 2
• Number of transitive dependencies: 3

Transitive dependencies:

1. Coprime
2. Integer Division Theorem
3. GCD is the smallest Linear Combination