# Property of congruence given a square-free modulus

Problem

Suppose $n$ is square-free and $\alpha,\beta,\gamma \in \mathbb{Z}_n$. I want to show that $\alpha^2 \beta = \alpha^2 \gamma \implies \alpha \beta = \alpha \gamma$.

Current Work

If $n$ is square free, then $n$ can be written as $n = \pm p_1 \cdots p_r$ where each $p_i$ is a distinct prime. Considering $\alpha^2 \beta \equiv \alpha^2 \gamma \mod n$, there are then two cases: $\gcd(\alpha,n) = 1$ or $\gcd(\alpha,n) \neq 1$.

Suppose $\gcd(\alpha,n) = 1$. Then $\alpha^{-1}$ exists in $\mathbb{n}$ and so $$\alpha^{-1}\alpha^2 \beta \equiv \alpha^{-1}\alpha^2 \gamma \mod n \implies \alpha\beta \equiv \alpha\gamma \mod n.$$

Suppose $\gcd(\alpha,n)\neq 1$. (stuck here)

Thoughts

In the first case can I really say that $\alpha\beta \equiv \alpha\gamma \mod n$ provides $\alpha \beta = \alpha \gamma$ as needed? I'm not quite sure if my approach is valid for this. Now in the second case, I am not sure how I should start; should I be considering an equivalence modulo $n/d$ where $d = \gcd(\alpha,n)$ so $\alpha,n$ are relatively prime? We can write $(\alpha/d)\alpha\beta = (\alpha/d)\alpha\gamma$, and since $n$ is square free, $n/\alpha$ will have no common factors with $(\alpha/d)\alpha$.

At that point, for $\alpha (\alpha\beta/d) \equiv \alpha (\alpha\gamma/d) \mod (n/d)$, there is an inverse $\alpha^{-1}$ in $\mathbb{Z}_{n/d}$ so $$\alpha^{-1}\alpha (\alpha\beta/d) \equiv \alpha^{-1}\alpha (\alpha\gamma/d) \mod (n/d) \implies \alpha\beta/d \equiv \alpha\gamma/d \mod (n/d).$$ This would then give me that $\alpha\beta \equiv \alpha\gamma \mod n$ and I am back to what I was unsure about in the first case.

• If say $n=pqr$, distinct primes, from $p$ divides $\alpha^2(\beta-\gamma)$ you can quickly conclude $p$ divides $\alpha(\beta-\gamma)$. (If a prime divides a product, it divides one of the terms.) Same is true of $q$, $r$, and any others. No need to treat the $\alpha$ and $n$ relatively prime case separately. Commented Aug 19, 2013 at 6:03

Note that it suffices to consider the case where $\alpha$ is prime. If you prove it for this case, given a composite $\alpha$, you can cancel its prime powers one at a time. Also note that by the Chinese Remainder Theorem, it suffices to prove that $$\alpha^2\beta=\alpha^2\gamma \mod p_i\Rightarrow \alpha\beta=\alpha\gamma \mod p_i$$
for each prime $p_i$. But, since $\alpha$ is one of the primes (I'm considering your second case), this is obvious. If $\alpha$ is $p_i$, then the above quantities remain zero mod $p_i$, and in every other modulus, $\alpha$ is invertible.