Results 1 to 2 of 2

Math Help - Question involving congruences and gcd's

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    152

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    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 [tex][/tex] will produce these images. For example, x^{2} \equiv 2 \; ( \text{mod } 4 ) is produced by [tex]x^{2} \equiv 2 \; (\text{mod } 4)[/tex]. 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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermat, Congruences, the CRT, and an exam question
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 24th 2011, 09:17 PM
  2. [SOLVED] Question about Linear Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2011, 12:10 PM
  3. I think this question is on congruences and RSA
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 01:35 AM
  4. Question about Linear Congruences
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 26th 2011, 11:09 AM
  5. question on distinct solutions to congruences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 17th 2008, 05:47 PM

Search Tags


/mathhelpforum @mathhelpforum