How do I rather quickly prove that $$a=2500137802, b=1420515313, c=3920653117$$ are relatively prime numbers? I know it has something to do with Euclidean algorithm, but still doesn't ring a bell to me.
Asked
Active
Viewed 101 times
0
-
Yes, this method I know, but it is not a rather quick proof and I would prefer someone showing me how to do this with reference to Euclidean algorithm. Thanks anyways. – John Robbers Feb 16 '17 at 18:01
-
1The Euclidean principle is that $\gcd(a,, b) =\gcd(a,, b-a)=\gcd(a,, b-\lfloor{b/a} \rfloor a)$: so you reduce $b$, then invert the couple and reduce $a$, etc. – G Cab Feb 16 '17 at 18:13
1 Answers
4
Hint $\ $ Any common divisor divides $\,2\, =\, 3920653117 -2500137802 - 1420515313$
Bill Dubuque
- 272,048
-
-
@John Are you trying to show that all three have no common divisor, or that they are pairwise coprime? – Bill Dubuque Feb 16 '17 at 18:05
-
-
@John Any common divisor divides the RHS above so it divides the LHS $= 2,$ so ..... – Bill Dubuque Feb 16 '17 at 18:08
-
It's becoming more clear for me now. I'm just learning this stuff, therefore it's really hard to understand everything, even though it looks simple and i feel daft, but thanks. :D – John Robbers Feb 16 '17 at 18:15
-
@John Suppose $,d,$ is a common divisor of $,a,b,c,$ Then $d$ also divides all integral linear combinations of them, i.e. $,d\mid ja+kb+nc,$ for all integers $,j,k,n.,$ The Euclidean algorithm is one efficient way to search for the least positive such linear combination, which is easily seen to be their gcd. The above exercise was constructed to help us quickly notice a very small linear combination $= 2.\ \ $ – Bill Dubuque Feb 16 '17 at 18:21