Results 1 to 3 of 3

Thread: Congruence Proof

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    3

    Congruence Proof

    If a $\displaystyle \equiv$ b (mod n), prove that gcd(b,n) = gcd(a,n).
    I've tried working with the relationship between these equations but haven't had much luck. Thanks for any help in advance!
    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,410
    Thanks
    1
    Let: $\displaystyle d_1 = \gcd (a,n) > 0$ and $\displaystyle d_2 = \gcd (b,n) > 0$

    By definition: $\displaystyle a \equiv b \ (\text{mod } m) \ \Leftrightarrow \ a = b + km$

    Since $\displaystyle d_1 \mid a$ and $\displaystyle d_1 \mid km$, then $\displaystyle d_1 \mid b$.

    But this means $\displaystyle d_1$ is a common divisor of both $\displaystyle b$ and $\displaystyle n$. Every common divisor of two integers divides their greatest common divisor.

    So: $\displaystyle d_1 \mid d_2$

    You can similarly show that: $\displaystyle d_2 \mid d_1$

    This implies: $\displaystyle d_1 = d_2$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,781
    Thanks
    3029
    Quote Originally Posted by o_O View Post
    Let: $\displaystyle d_1 = \gcd (a,n) > 0$ and $\displaystyle d_2 = \gcd (b,n) > 0$

    By definition: $\displaystyle a \equiv b \ (\text{mod } m) \ \Leftrightarrow \ a = b + km$

    Since $\displaystyle d_1 \mid a$ and $\displaystyle d_1 \mid km$, then $\displaystyle d_1 \mid b$.
    You mean "n", not "m" here, don't you?

    But this means $\displaystyle d_1$ is a common divisor of both $\displaystyle b$ and $\displaystyle n$. Every common divisor of two integers divides their greatest common divisor.

    So: $\displaystyle d_1 \mid d_2$

    You can similarly show that: $\displaystyle d_2 \mid d_1$

    This implies: $\displaystyle d_1 = d_2$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Apr 22nd 2010, 02:50 PM
  2. Congruence proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 10th 2009, 10:03 AM
  3. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jun 5th 2009, 09:34 AM
  4. Congruence proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Mar 24th 2008, 07:16 AM
  5. Proof congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Nov 19th 2007, 09:13 AM

Search Tags


/mathhelpforum @mathhelpforum