1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Co-Primes Proof

  1. May 19, 2014 #1
    1. The problem statement, all variables and given/known data
    Let ##n \in \mathbb{Z} , n \not | 3##. Prove that ##gcd( n , n +3 ) =1 ##

    3. The attempt at a solution
    If n is not divisible by 3, then
    n = 3k+1 or n =3k+2 , ## k \in \mathbb{Z} ##

    What is a feasible approach? Can I do this?
    For first case,
    ## gcd(3k+1, 3k+4 ) = 1 \\ \exists s,t \in \mathbb{Z} \\ 1 =(3k+1)s + (3k+4)t ##
     
  2. jcsd
  3. May 19, 2014 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I would just use the definition. Assume that there is an integer ##d## that divides both ##n## and ##n+3##, then...
     
  4. May 19, 2014 #3
    Thanks.

    You mean state Euclid's lemma?
    Let ## a,b,c \in \mathbb{Z} \wedge a \not = 0 ## . If ## a|bc \wedge gcd(a,b) =1 , ##then ## a|c ##

    ## n | (n+3)c , c \in \mathbb{Z} \\ n| c##?
     
  5. May 19, 2014 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I don't see how this is applicable here. Just use the definitions.
     
  6. May 19, 2014 #5
    ## d| n+3 \\ d|n \\ n =dk \wedge n +3 = dp, p,k \in \mathbb{Z} \\ 3=d(p-k) ##


    Since p-k is an integer, d|3 ?
    I don't get where is the connection of ##d## with ##n## not divisible by 3.
     
  7. May 19, 2014 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Ok, so you found that ##d## divides ##3##. Can you then list all the possible values that ##d## can be?
     
  8. May 19, 2014 #7
    Since 3 is prime d can be 1 or 3.
     
  9. May 19, 2014 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    So you need to prove that ##d=3## can't happen.
     
  10. May 19, 2014 #9
    So,

    ## d=3 \\ n =3k \\ n+3 =3p \\ gcd(n, n+3 ) =1 \\ nh + (n+3)x =1, h,x \in \mathbb{Z} \\ 3(kh+px) =1, kh+px \in \mathbb{Z} ##


    Then, 3|1; however, 1 =3y is impossible, since y must be integer.
    So, necessarily d =1 only.

    I still don't see the connection. Are we assuming that ## d \equiv n##?
     
  11. May 19, 2014 #10

    Curious3141

    User Avatar
    Homework Helper

    Again, you're overthinking the problem.

    If a number divides two distinct numbers, then it also divides their difference. Hence d divides 3. Since 3 is prime, that means d can be 3 or 1.

    Since d divides n, and d = 3, does 3 divide n? Does that violate any of the stipulations of the question? What does that leave you with as a possible value of d?
     
  12. May 19, 2014 #11
    So, d | n
    d =3

    does 3 |n ?
    Well, the stipulations say that ##n## is not divisible by 3. ## n\not | 3 ##
    Sorry, but again I am lost.
    ## (n = 3k )\not = (3 \not = np), k,p \in \mathbb{Z} ##
     
  13. May 19, 2014 #12

    Curious3141

    User Avatar
    Homework Helper

    You KNOW that ##d \mid n.## (Fact 1)

    You KNOW that ##d \mid 3.## (Fact 2)

    You KNOW that ##3 \nmid n.## (Fact 3)

    Fact 2 implies that ##d=1## (possibility 1) or ##d=3## (possibility 2) because 3 is prime.

    IF possibility 2 were true, THEN by Fact 1, ##3 \mid n##. But this cannot be so because it would conflict with Fact 3. Therefore possibility 2 is rejected.

    That leaves only possibility 1, i.e. ##d=1##. The only possible common divisor for ##n## and ##n+3## where ##3 \nmid n## is 1. Therefore, this is also the greatest common divisor.

    By the way, you're using the non-divisibility notation wrongly. If you want to state that n is not divisible by 3, it should be ##3 \nmid n## (read as '3 does not divide n', or '3 is not a divisor of n').
     
  14. May 20, 2014 #13
    Thank you very much, Curious.
    BTW, that cat in your pic looks happy :>
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Co-Primes Proof
  1. Prime Number Proof (Replies: 5)

  2. Prime number proof (Replies: 3)

Loading...