Results 1 to 8 of 8

Math Help - Proofs USING GCDs

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    33

    Proofs USING GCDs

    Let m and n be integers with n >= m > 0. Set d = Gcd(m, n).

    A)Prove that if c|m and c|n, then c|d.

    B)For any integer q, prove d = Gcd(m, n − qm) by proving each side divides the other.

    its kinda obvious that they are true and work
    but don't know how to proove them
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Chicago, IL
    Posts
    2,844
    Thanks
    3
    Quote Originally Posted by AwesomeDesiKid View Post
    Let m and n be integers with n >= m > 0. Set d = Gcd(m, n).

    A)Prove that if c|m and c|n, then c|d.

    B)For any integer q, prove d = Gcd(m, n − qm) by proving each side divides the other.

    its kinda obvious that they are true and work
    but don't know how to proove them
    For A), note that \gcd\!\left(m,n\right)=sm+tn for some s,t\in\mathbb{Z}. So if c\mid m and c\mid n, then c\mid \gcd\!\left(m,n\right) since \gcd\!\left(m,n\right) is a linear combination of m and n.

    Does this make sense so far?

    For B) use the fact that \gcd\!\left(a,b\right)=sa+tb for some s,t\in\mathbb{Z} to show the desired result (I leave it for you to figure this part out).

    Does this make sense?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2009
    Posts
    33
    Quote Originally Posted by Chris L T521 View Post
    For A), note that \gcd\!\left(m,n\right)=sm+tn for some s,t\in\mathbb{Z}. So if c\mid m and c\mid n, then c\mid \gcd\!\left(m,n\right) since \gcd\!\left(m,n\right) is a linear combination of m and n.

    Does this make sense so far?

    For B) use the fact that \gcd\!\left(a,b\right)=sa+tb for some s,t\in\mathbb{Z} to show the desired result (I leave it for you to figure this part out).

    Does this make sense?
    Can you break/explain it little bit in details
    like why do u do that, so if i see that kinda problem in future i would know how to pick it up
    THANKS
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Sorry for hijacking.

    Linear combination is useful because you can factor things out. If c\mid m and c\mid n, then for any integers s, t, you can factor out c from sm + tn. Let's call this fact C).

    For B), the problem statement suggests proving that both sides divide each other. By C), c\mid m and c\mid n implies c\mid (n-qm). So, using A), we have d\mid\gcd(m, n-qm). Conversely, we need \gcd(m, n-qm)\mid d. Obviously, \gcd(m, n-qm)\mid m and \gcd(m, n-qm)\mid (n-qm). By C), this implies that \gcd(m, n-qm)\mid n because n is a linear combination of m and n-qm. So, again by A), \gcd(m, n-qm)\mid d.

    Feel free to ignore the rest; I am writing sort of to recall these things for myself.

    I prefer proving B) first and then A). B) is easy: by C), the pairs (n, m) and (m, n - qm) have the same set of common divisors (at least when n - qm \ge 0 to avoid possible problems with the definition of divisors of negative numbers). Therefore, the greatest of those divisors is the same.

    To show A), as well as the fact that \gcd(n,m) is a linear combination of n and m, one uses Euclid's algorithm for computing GCD. The algorithm repeatedly changes a pair (n, m) into (m, n - qm) and applies C) or B). Each step preserves the set of common divisors of the pair. We stop when (d, 0) is reached. Why is d the GCD of the original numbers? Because by the described preservation, every common divisor of the original numbers, including the GCD, is a common divisor of (d, 0), i.e., a divisor of d, and vice versa.

    Am I missing something in this reasoning?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2009
    Posts
    33
    Quote Originally Posted by emakarov View Post
    Sorry for hijacking.

    Linear combination is useful because you can factor things out. If c\mid m and c\mid n, then for any integers s, t, you can factor out c from sm + tn. Let's call this fact C).

    For B), the problem statement suggests proving that both sides divide each other. By C), c\mid m and c\mid n implies c\mid (n-qm). So, using A), we have d\mid\gcd(m, n-qm). Conversely, we need \gcd(m, n-qm)\mid d. Obviously, \gcd(m, n-qm)\mid m and \gcd(m, n-qm)\mid (n-qm). By C), this implies that \gcd(m, n-qm)\mid n because n is a linear combination of m and n-qm. So, again by A), \gcd(m, n-qm)\mid d.

    Feel free to ignore the rest; I am writing sort of to recall these things for myself.

    I prefer proving B) first and then A). B) is easy: by C), the pairs (n, m) and (m, n - qm) have the same set of common divisors (at least when n - qm \ge 0 to avoid possible problems with the definition of divisors of negative numbers). Therefore, the greatest of those divisors is the same.

    To show A), as well as the fact that \gcd(n,m) is a linear combination of n and m, one uses Euclid's algorithm for computing GCD. The algorithm repeatedly changes a pair (n, m) into (m, n - qm) and applies C) or B). Each step preserves the set of common divisors of the pair. We stop when (d, 0) is reached. Why is d the GCD of the original numbers? Because by the described preservation, every common divisor of the original numbers, including the GCD, is a common divisor of (d, 0), i.e., a divisor of d, and vice versa.

    Am I missing something in this reasoning?
    no, its good, but how would u put it in to "MATH" language
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    It is already in the math language if by this you mean the style that combines text and formulas and is used, say, in math textbooks. It is possible to write this using symbols only, without words, but it won't be easier to understand.

    If you need more details and smaller steps from one statement to the next, could you post the exact place which you understand? For example:
    You write:
    Obviously,
    I don't understand why this the case.
    Or:
    You write:
    By C), this implies that
    I cannot figure out how to use C) to derive from the previous statement.
    If, on the other hand, the whole text does not make sense, then you probably need to go back to definitions, examples and simple exercises to build some intuition about these things.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by AwesomeDesiKid View Post
    Let m and n be integers with n >= m > 0. Set d = Gcd(m, n).

    A)Prove that if c|m and c|n, then c|d.

    B)For any integer q, prove d = Gcd(m, n − qm) by proving each side divides the other.

    its kinda obvious that they are true and work
    but don't know how to proove them
    emarakov is no doubt on the right path. Just to clean it up a bit.

    Problem: Let (m,n)=d. Prove that c|m,n\implies c|d

    Proof: Since (m,n)=d we konw that the linear Diophantine equation mx+ny=d has a solution (x_0,y_0)\in\mathbb{Z}^2. Therefore, mx_0+ny_0=d. But if c|m,n it is clear that c|mx_0,ny_0 thus c|mx_0+ny_0=d.


    Problem: Define m,n,d as in the last problem and prove that d=(m,n-qm) by proving they divide each other.

    Proof: Since d|m,n it is clear that d|m\text{ and }d|n-qm. Therefore d is a divisor of m\text{ and }n-qm thus d|(m,n-qm). Now note that (m,n-qm)|m by definition, and since (m,n-qm)|qm and n-qm is an integer it is clear that (m,n-qm)|n. Thus, (m,n-qm) is a divisor of m\text{ and }n so (m,n-qm)|d. The conclusion follows.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2009
    Posts
    33
    Quote Originally Posted by Drexel28 View Post
    emarakov is no doubt on the right path. Just to clean it up a bit.

    Problem: Let (m,n)=d. Prove that c|m,n\implies c|d

    Proof: Since (m,n)=d we konw that the linear Diophantine equation mx+ny=d has a solution (x_0,y_0)\in\mathbb{Z}^2. Therefore, mx_0+ny_0=d. But if c|m,n it is clear that c|mx_0,ny_0 thus c|mx_0+ny_0=d.


    Problem: Define m,n,d as in the last problem and prove that d=(m,n-qm) by proving they divide each other.

    Proof: Since d|m,n it is clear that d|m\text{ and }d|n-qm. Therefore d is a divisor of m\text{ and }n-qm thus d|(m,n-qm). Now note that (m,n-qm)|m by definition, and since (m,n-qm)|qm and n-qm is an integer it is clear that (m,n-qm)|n. Thus, (m,n-qm) is a divisor of m\text{ and }n so (m,n-qm)|d. The conclusion follows.
    thank you so much, this is sooooo much more clear
    not that emarakov wan't big help, but this one i can see soo clearly
    thanks again
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. GCDs and LCMs
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 16th 2011, 08:45 PM
  2. On GCDs and power's of 2
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 16th 2010, 03:19 AM
  3. GCDs of polynomials
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 29th 2010, 08:38 PM
  4. gcds
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 6th 2008, 02:11 PM
  5. Replies: 3
    Last Post: October 6th 2007, 03:01 PM

Search Tags


/mathhelpforum @mathhelpforum