# Thread: Question involving congruences and gcd's

1. ## 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.

2. 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, $\displaystyle 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: $\displaystyle ax \equiv ay \ (\text{mod } n) \ \Leftrightarrow \ ax = ay + kn$ for some $\displaystyle k \in \mathbb{Z}$

Since $\displaystyle d = (a,n)$, we can divide both sides by $\displaystyle d$: $\displaystyle \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 $\displaystyle w \mid st$ and $\displaystyle (w, s) = 1$, then $\displaystyle w \mid t$.

Can you finish?