1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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
    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
    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
    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
    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 :>
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Loading...