Results 1 to 14 of 14

Math Help - gcd(n, n+p)

  1. #1
    Member mohammadfawaz's Avatar
    Joined
    Feb 2010
    From
    Lebanon - Beirut
    Posts
    100

    gcd(n, n+p)

    Hello all,
    Given a prime number p and an integer n. Prove that gcd(n, n+p) is either 1 or p.
    If p is less than n, then we have two cases: either n is a multiple of p, and then we'll get that the gcd is equal to p, or n is not a multiple of p, and then we'll get that the gcd is equal to 1.
    However, if n is less than p, then we must get a 1 (we can't get p since p>n). I didn't figure out how to prove that! Need your help!

    Thank you

    Mohammad
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Actually it's quite simple if you approach the problem differently... No need for examination of cases.

    gcd(n,n+p) by definition divides both n and p ; thus it also divides their difference, (n+p)-n.
    Hence gcd(n,n+p) divides p . But since p is prime gcd(n,n+p) is equal to either 1 or p (the only divisors of p .)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Let the gcd(n,n+p)=d

    Since d is a common divisor, n=md \ \mbox{and} \  n+p=rd such that n,m\in\mathbb{Z}.

    Then by addition we obtain n+(n+p)=d(m+r)\Rightarrow d|[n+(n+p)].

    Now, d|n \ \mbox{and} \ d|(n+p)

    Thus, it is trivial that 1 divides n and n+p.

    Now, since d|(n+p), \ \mbox{then} \ d|n \ \mbox{and} \ d|p

    Since p is prime, d can only be 1 or p.
    Last edited by dwsmith; December 11th 2010 at 10:00 PM. Reason: Removed d such that ... due to Tonio's observation
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by dwsmith View Post
    Let the gcd(n,n+p)=d such that d is either 1 or p.


    You can't begin a proof by assuming that what you want to prove is true...!


    Since d is a common divisor, n=md \ \mbox{and} \  n+p=rd such that n,m\in\mathbb{Z}.

    Then by addition we obtain n+(n+p)=d(m+r).

    Now, d|n \ \mbox{and} \ d|(n+p)

    Thus, it is trivial that 1 divides n and n+p.


    "Thus"? this is trivial and it doesn't follow from the above!

    I think Melese's proof is correct, short and pretty concise. Nothing more is needed and

    the above (and below) doesn't add, imo, any clearity to this matter.

    Tonio


    Now, since d|(n+p), \ \mbox{then} \ d|n \ \mbox{and} \ d|p

    Since p is prime, d can only be 1 or p.
    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    You are correct about saying d is 1 and p but I beg to differ on the rest.

    Doesn't follow from above?

    d(m+r)=dq where q=m+r. Now, dq=[n+(n+p)]\Rightarrow d|[n+(n+p)]\Rightarrow d|n \ \mbox{and} \ d|(n+p)

    Clearly, if d is 1, it is true sinc 1|n\Rightarrow 1*k=n, \ k=n \ \mbox{and} \ 1*t=n+p, \ t=n+p

    Thus, 1 is a trivial case since it always works.

    Now, examining d|(n+p)\Rightarrow d|n \ \mbox{and} \ d|p which leads d=1 or p since 1 or the prime number divides p.

    Also, it does add value. Not everyone thinks the same way and I don't prefer Melese proof. That doesn't mean I discredit his work. I appreciate it his work since it has benefited me in the past.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by dwsmith View Post
    You are correct about saying d is 1 and p but I beg to differ on the rest.

    Doesn't follow from above?

    d(m+r)=dq where q=m+r. Now, dq=[n+(n+p)]\Rightarrow d|[n+(n+p)]\Rightarrow d|n \ \mbox{and} \ d|(n+p)


    No, by all means no!! It isn't true at all that d\mid [n+(n+p)]\Longrightarrow d\mid n\,\,and\,\,d\mid (n+p) .

    For example, take d=3\,,\,n=1\,,\,p=19.\,\,Then\,\,3\mid 1+(1+19)\,,\,\,but\,\,3\nmid 1\,\,and\,\,3\nmid (1+19) !


    Clearly, if d is 1, it is true sinc 1|n\Rightarrow 1*k=n, \ k=n \ \mbox{and} \ 1*t=n+p, \ t=n+p

    Thus, 1 is a trivial case since it always works.

    Now, examining d|(n+p)\Rightarrow d|n \ \mbox{and} \ d|p


    Again, this doesn't follow!

    I think you must check your logical deductions in this matter very carefully.

    Tonio


    which leads d=1 or p since 1 or the prime number divides p.

    Also, it does add value. Not everyone thinks the same way and I don't prefer Melese proof. That doesn't mean I discredit his work. I appreciate it his work since it has benefited me in the past.
    .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    If n=1 and n+p=20, the gcd(1,20)\neq 3
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by dwsmith View Post
    If n=1 and n+p=20, the gcd(1,20)\neq 3

    Who cares?! You wrote A\Longrightarrow B and, as shown in my past post, this is false. In mathematics such a thing

    doesn't force you to go back all the way, [U]unless[U] you specifically write so, and you didn't (and well

    done since in this case that wouldn't work either)

    Tonio
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    If we are given gcd(a,b)=m, then m|a \ \mbox{and} \ m|b.

    Now, if we have the gcd(n,n+p)=d, then gcd\left(\frac{n}{d},\frac{n+p}{d}\right)=1.

    Therefore, d|n \ \mbox{and} \ d|(n+p)
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by dwsmith View Post
    If we are given gcd(a,b)=m, then m|a \ \mbox{and} \ m|b.

    Now, if we have the gcd(n,n+p)=d, then gcd\left(\frac{n}{d},\frac{n+p}{d}\right)=1.

    Therefore, d|n \ \mbox{and} \ d|(n+p)

    Now that is true, but it's way different from what you wrote the first time...can you tell?

    And again, you make things messier than necessary: what does "Now, if we have the gcd(n,n+p)=d\,\,then\,\,gcd(n/d,(n+p)/d)=1"

    have to do with this?? Simply, by definition, gcd(n,n+p)=d\Longrightarrow d\mid n\,,\,d\mid (n+p) , period.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Would you accept my OP if I added the definition in?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by dwsmith View Post
    Would you accept my OP if I added the definition in?

    No. It is flawed from the beginning and all through, and you didn't actually prove anything.

    When I said that Melese's proof is nice is because it's the shortest and clearest I know, not

    comparing it with yours since yours is not a proof.

    I'm not trying to offend or hurt, I'm just pointing out a fact.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    You still haven't convinced me it is wrong though.

    Since d|n and d|(n+p), of course 1 is a possible solution.

    gcd(n,p)=y

    y|n and y|p but we also know d|n

    y|(n+p) but d|(n+p) so y=d.

    Since y=d, d|p. d*h=p and p is prime so only 1 and the actually prime number, p, will divide p.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by dwsmith View Post
    Let the gcd(n,n+p)=d

    Since d is a common divisor, n=md \ \mbox{and} \  n+p=rd such that n,m\in\mathbb{Z}.

    Then by addition we obtain n+(n+p)=d(m+r)\Rightarrow d|[n+(n+p)].

    Now, d|n \ \mbox{and} \ d|(n+p)

    Thus, it is trivial that 1 divides n and n+p.

    Now, since d|(n+p), \ \mbox{then} \ d|n \ \mbox{and} \ d|p

    Since p is prime, d can only be 1 or p.

    Ok then. I really think you honestly believe that what you wrote is correct in some sense, and I'll try to show you that

    you're wrong. The above is your first post, and let's try to analyze it carefully, shall we?

    To begin with, to establish as assumption what has to be proved is incorrect, as we already agreed, and as I can see

    you already erased it and some other stuff. Good.

    Next, lines 2 and 3 are completely innecessary except for the very last part of line 3 (and even then it

    should better be a rest and not a sum), since what's written in line 4 follows directly from line 1, i.e. from gcd(n,n+p)=d .

    Line 5 is wrong from a logical and semantic point of view: that "thus" there renders false the whole line. The number 1 divides

    ANYTHING in \mathbb{Z} , whether what you wrote in lines 2,3,4 is false or true. Writing that thus makes

    the whole thing even more confusing and false, since it does NOT follow from line 4!

    Line 6 is plainly false: it doesn't follow that d\mid n\,\,and\,\,d\mid p from d\mid(n+p) . It follows from d\mid n\,\,and\,\,\d\mid (n+p)\Longrightarrow d\mid [(n+p)-p=p] .

    In particular, that "then" before d\mid n is very confusing, since, again, this follows from the

    very definition of gcd and from line 1 !, not from the first part of line 6.

    Resuming Melese's proof, it is the simplest thing: (n,n+p)=d\Longrightarrow d\mid n\,,\,d\mid (n+p)\Longrightarrow d\mid [(n+p)-n=p]\Longrightarrow d\mid p\Longleftrightarrow d=1\,\,or\,\,p

    Tonio
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum