Results 1 to 6 of 6

Math Help - prove Euclidean Algorithm based ...

  1. #1
    Member
    Joined
    May 2008
    Posts
    102
    Awards
    1

    Smile prove Euclidean Algorithm based ...

    Q1) prove that if d is a positive integer, d\a and d\b, then (a,b) = d...if and only if (d\a, d\b) = 1.

    Q2) Prove that if P is a prime and a is an integer, and p does not divide a then (a,p) = 1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by Vedicmaths View Post
    Q1) prove that if d is a positive integer, d\a and d\b, then (a,b) = d...if and only if (d\a, d\b) = 1.
    These notations look weird to me...

    For "d divides a", I'd say d|a or d\a.
    But for \frac da, it's rather d/a..

    Are you allowed to use Bézout's identity ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    102
    Awards
    1

    Smile

    yeah I am sorry...that form is d divides a and d divides b...I messed up with my signs!

    I don't think so we have studied this before! I think we have to use the division algorithm for that purpose...
    but I tried solving it...please approve if that makes sense or help me out!

    when we say the common divisor of a and b is d it means this:
    a = d * x
    b = d * y
    so when we divide a on d ( a/d) 'x' would remain.
    in other words x = a / d
    and in the same way when we divide a on d (a/d) y would remain. in other words y = b/ d
    note that (x, y)= 1 because if it wasn't 1 the greatest divisor of a and b would be more than d ( for example if (x,y)= s we would have (a, b) = (dx, dy) = d*(x,y)= d*s)
    so (x,y)=1
    and (a/d , b/d)= ( x , y)=1...

    Thanks for offering help!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    It looks confusing to me... though it looks correct ^^

    ------------------------------
    Known fact : d is a common divisor of a and b.

    We want to prove \underbrace{(a,b)=d}_{\color{red}A} \Leftrightarrow \underbrace{(x,y)=1}_{\color{red}B}, where x and y are defined like you did

    Proving A \Rightarrow B ~:~ (a,b)=d \Rightarrow (x,y)=1
    It corresponds to what you've written here :
    note that (x, y)= 1 because if it wasn't 1 the greatest divisor of a and b would be more than d ( for example if (x,y)= s we would have (a, b) = (dx, dy) = d*(x,y)= d*s)
    so (x,y)=1
    and (a/d , b/d)= ( x , y)=1...
    The thing is that it's not very good to sa "it's that because if it was not..."
    What you've done is sort of proving the contrapositive.

    Suppose (x,y)=s > 1. Then (a,b)=(dx,dy)=d(x,y)=ds \neq d
    So we have proved that \color{red} \overline B \Rightarrow \overline A, which is equivalent to A \Rightarrow B.

    Yes, it looks like it's a lot, but I'm just trying to explain as much as possible the reasoning


    Proving A \Leftarrow B ~:~ (a,b)=d \Leftarrow (x,y)=1
    If (x,y)=1, then (dx,dy)=d... The rest follows
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Vedicmaths View Post
    Q2) Prove that if P is a prime and a is an integer, and p does not divide a then (a,p) = 1.
    We want to prove p \nmid a \implies (a,p)=1

    And we are going to prove the contrapositive (equivalent to the initial implication), that is to say :

    (a,p) \neq 1 \implies p \mid a

    -------------------------
    (a,p) \neq 1 \Leftrightarrow \text{ There exists d} > \text{1, such that (a,p)=d.}

    Therefore, d divides a and p.

    But the only divisors of p are 1 and p itself.
    We said that d > 1, so it cannot be 1.

    Thus d=p.

    --> p \text{ divides } a \quad \text{Q.E.D.}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2008
    Posts
    102
    Awards
    1
    thanks a lot Moo!
    yeah I kinda figured it out that I have not mentioned enough about what I knew. but yeah what you have written totally makes sense and its kinda cool way to say qed!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 06:53 AM
  2. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 06:45 PM
  3. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 19th 2010, 11:13 AM
  4. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 29th 2009, 11:51 AM
  5. Euclidean Algorithm
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 7th 2006, 11:25 AM

Search Tags


/mathhelpforum @mathhelpforum