Results 1 to 6 of 6

Math Help - x≡y (mod a) => (x,a)=(y,a)

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    14

    x≡y (mod a) => (x,a)=(y,a)

    Looking at the following one would think it is simple, and mabye it is, BUT to me it is impossible and has been so for two days.

    So, show that if x≡y (mod a) then (x,a)=(y,a)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3
    Dear matzerath,

    Suppose, d_1=(x,a) and d_2=(y,a)

    x\equiv{y(mod a)}\Rightarrow{a}\mid{x-y}

    Therefore, d_1\mid{a} and a\mid{x-y}\Rightarrow{d_1\mid{x-y}}

    d_1\mid{x-y} and d_1\mid{x}\Rightarrow{d_1\mid{y}}

    d_1 is a common divisor of y and a

    Therefore, d_1\leq{d_2}--------(1)


    Similarly, d_2 is a common divisor of x and a

    Therefore, d_2\leq{d_1}---------(2)

    From (1) and (2),

    d_1=d_2\Rightarrow{(x,a)=(y,b)}

    Hope this helps.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    106
    There's a short way to prove this.
    k\in \mathbb{Z})" alt="x\equiv y \pmod{a} \Leftrightarrow x=y+ka\:\k\in \mathbb{Z})" />
    Thus, using the fact that \gcd(m,n)=\gcd(m+rn,n) for all r\in \mathbb{Z}, it follows that

    \gcd(x,a)=\gcd(y+ka,a)=\gcd(y,a)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2010
    Posts
    14
    Quote Originally Posted by Unbeatable0 View Post
    There's a short way to prove this.
    k\in \mathbb{Z})" alt="x\equiv y \pmod{a} \Leftrightarrow x=y+ka\:\k\in \mathbb{Z})" />
    Thus, using the fact that \gcd(m,n)=\gcd(m+rn,n) for all r\in \mathbb{Z}, it follows that

    \gcd(x,a)=\gcd(y+ka,a)=\gcd(y,a)

    how would one prove the last thing? I've seen it before but I've never seen the proof...

    and by the last thing I mean \gcd(y+ka,a)=\gcd(y,a)

    Yeah, and thanks to both of you!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3
    Dear matzerath,

    Suppose, (y+ka,a) = d_1 and (y,a) = d_2 for k\in{Z}

    Since, (y+ka,a) = d_1

    d_1\mid{y+ka} and d_1\mid{a}

    Therefore, d_1\mid{y} and d_1\mid{a}

    d_1\leq{d_2}--------(1)

    Also since, d_2=(y,a)

    d_2\mid{y} and d_2\mid{a}

    Therefore, d_2\mid{y+ka} and d_2\mid{a}

    d_2\leq{d_1}---------(2)

    By (1) and (2); d_1=d_2\Rightarrow{(y+ka,a)=(y,a)}

    Hope this helps.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2010
    Posts
    14
    Quote Originally Posted by Sudharaka View Post
    Dear matzerath,

    Suppose, (y+ka,a) = d_1 and (y,a) = d_2 for k\in{Z}

    Since, (y+ka,a) = d_1

    d_1\mid{y+ka} and d_1\mid{a}

    Therefore, d_1\mid{y} and d_1\mid{a}

    d_1\leq{d_2}--------(1)

    Also since, d_2=(y,a)

    d_2\mid{y} and d_2\mid{a}

    Therefore, d_2\mid{y+ka} and d_2\mid{a}

    d_2\leq{d_1}---------(2)

    By (1) and (2); d_1=d_2\Rightarrow{(y+ka,a)=(y,a)}

    Hope this helps.

    next time I'll think befor asking a question... but thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a ≡ b ?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 7th 2011, 01:06 AM
  2. Replies: 0
    Last Post: June 28th 2010, 08:32 PM
  3. a^p≡1 (mod p^n) iff a≡1 (mod p^(n-1)), n≥2
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 8th 2010, 08:59 AM
  4. lcm of k,k+1,k+2 where k≡3(mod 4)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 12th 2010, 01:46 PM
  5. x^n ≡ 3 (mod 4) only if x ≡ n ≡ 1 (mod 2)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 30th 2010, 04:24 AM

Search Tags


/mathhelpforum @mathhelpforum