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)


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.

  • $\begingroup$ 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. $\endgroup$ – André Nicolas Aug 19 '13 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.