Results 1 to 4 of 4

Math Help - GCD=1 with Congruence

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    GCD=1 with Congruence

    Let a,b,c,n be integers with n>1. If gcd(a,n)=1, ab congruences ac (mod n).

    Prove b congruence c (mod n).

    My proof so far:

    Now I have ai + nj = 1 and ab = ac+ne for integers i,j,e.

    Then I need something like b = c + nv for an integer v.

    How do I go for that?

    Thanks.

    KK
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by tttcomrader View Post
    Let a,b,c,n be integers with n>1. If gcd(a,n)=1, ab congruences ac (mod n).

    Prove b congruence c (mod n).

    My proof so far:

    Now I have ai + nj = 1 and ab = ac+ne for integers i,j,e.

    Then I need something like b = c + nv for an integer v.

    How do I go for that?

    Thanks.

    KK
    I am sure you learn this in class.

    Theorem
    Let the integers be positive then,
    ac=bc (mod n)
    Then
    a = b (mod n/d) where d=gcd(n,c)

    Thus, in the special case of relative primeness we have d=1.
    Simple.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    N0, I have not learn this theorem in class yet.

    Is there a proof somewhere in the web?

    KK
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by tttcomrader View Post
    N0, I have not learn this theorem in class yet.

    Is there a proof somewhere in the web?

    KK
    Use Euclid's Lemma (assuming you proved it in class).

    Theorem Given positive integers, if a|(bc) and gcd(a,b)=1 then a|c.

    Proof I leave it as an excerise for you to prove, if you did not.

    Corollary If ac=bc (mod n) and gcd(c,n)=1 then a=b (mod n). Given positive integers.

    Proof By definition n|(ac-bc) then n|c(a-b) but gcd(c,n)=1 thus we have n|(a-b) by Euclid's Lemma. Thus, by definition a=b (mod n).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: May 12th 2009, 11:19 AM
  2. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 02:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 06:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 10:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 11:57 AM

Search Tags


/mathhelpforum @mathhelpforum