# Question involving congruences and gcd's

• Nov 18th 2008, 03:42 PM
Janu42
Question involving congruences and gcd's
Let a, x, n, y in Z, n>1. Prove that if ax is congruent to ay(mod n), then x is congruent to y (mod n/d), where d = (a,n).

Question: How do I do the congruence equal sign thing, and other stuff like that. Also, a, x, n, y in Z. How do I do the symbol to show they are in the set Z? Thanks.
• Nov 18th 2008, 05:23 PM
o_O
Welcome to MHF! Hope you find this forum a helpful resource. If you are satisified with any of the help you receive here, show your gratitude by clicking the 'Thanks' button beneath a post or simply leaving a thank you!

To produce these math symbols, take a look at this tutorial: LaTex Tutorial

Basically, wrapping coding around  will produce these images. For example, $x^{2} \equiv 2 \; ( \text{mod } 4 )$ is produced by $$x^{2} \equiv 2 \; (\text{mod } 4)$$. If you want to see the coding behind an image, just click on it!

_________________________

As for your question: $ax \equiv ay \ (\text{mod } n) \ \Leftrightarrow \ ax = ay + kn$ for some $k \in \mathbb{Z}$

Since $d = (a,n)$, we can divide both sides by $d$: $\frac{a}{d}x = \frac{a}{d}y + k\left(\frac{n}{d}\right) \ \Leftrightarrow \ \frac{n}{d} \mid \frac{a}{d}(x-y)$

Now use the fact that if $w \mid st$ and $(w, s) = 1$, then $w \mid t$.

Can you finish?