d2jsp
Log InRegister
d2jsp Forums > Off-Topic > General Chat > Homework Help > Prime Numbers > Are Two Primes Always Relatively Prime?
Add Reply New Topic New Poll
Member
Posts: 5,207
Joined: Dec 6 2009
Gold: 24,204.00
Feb 26 2014 05:19pm
Are two primes always relatively prime? I'm having trouble proving this with contradiction.

First I assume that two primes, p and q are not relatively prime. Therefore there is an x > 1 that divides both p and q.

x | p ... so p = xk

x | q ... so q = xd

Am I on the right track? I think what I need to do is show that x = 1 but I'm not sure how to get there
Member
Posts: 5,942
Joined: Mar 29 2012
Gold: 7,561.46
Feb 26 2014 05:31pm
if p and q are prime numbers, p is dividable only by 1 and p, and q is dividable only by 1 and q. so the only thing that can divide both is 1, unless p=q to begin with :wacko: not sure it needs a better proff than this, its quite logical to me
Member
Posts: 5,207
Joined: Dec 6 2009
Gold: 24,204.00
Feb 26 2014 05:37pm
Quote (Snyft @ Feb 26 2014 06:31pm)
if p and q are prime numbers, p is dividable only by 1 and p, and q is dividable only by 1 and q. so the only thing that can divide both is 1, unless p=q to begin with :wacko: not sure it needs a better proff than this, its quite logical to me


yeah it makes sense logically to me I just can't seem to find a way to prove it rigorously
Member
Posts: 5,942
Joined: Mar 29 2012
Gold: 7,561.46
Feb 26 2014 05:39pm
Quote (Bloo_Guardian @ Feb 27 2014 01:37am)
yeah it makes sense logically to me I just can't seem to find a way to prove it rigorously


but this kinda proves it, for example take numbers 4 and 22, 4=2*2 and 22=2*11, so the common is 2

with p and q you just have 1*p and 1*q and thats where it ends :wacko: i mean i like mathematical proving, but this is just so fucking obvious i think this should do :wacko:
Member
Posts: 28,331
Joined: Jun 9 2007
Gold: 11,700.00
Feb 26 2014 05:48pm
Quote (Bloo_Guardian @ 26 Feb 2014 23:37)
yeah it makes sense logically to me I just can't seem to find a way to prove it rigorously


seems you have been given a problem, can be you please state it exactly as it is given to you
Member
Posts: 5,207
Joined: Dec 6 2009
Gold: 24,204.00
Feb 26 2014 05:49pm
True/False? Any pair of primes is relatively prime.
Member
Posts: 5,942
Joined: Mar 29 2012
Gold: 7,561.46
Feb 26 2014 05:51pm
Quote (Bloo_Guardian @ Feb 27 2014 01:49am)
True/False? Any pair of primes is relatively prime.


truuuue, unless they are identical numbers!
Member
Posts: 28,331
Joined: Jun 9 2007
Gold: 11,700.00
Feb 26 2014 05:52pm
Quote (Bloo_Guardian @ 26 Feb 2014 23:49)
True/False? Any pair of primes is relatively prime.


the answer is true, as you probably know
what is the definition of a,b being co-prime (ie relatively prime)? gcd(a,b)=1
and what is the definition of a prime p? gcd(p,n)=1 for all n=/=p
Member
Posts: 5,207
Joined: Dec 6 2009
Gold: 24,204.00
Feb 26 2014 06:01pm
okay thank you
Go Back To Homework Help Topic List
Add Reply New Topic New Poll