I was trying to solve the task of checking if 2 numbers have same prime divisors. For example 10 has prime divisors of 2 and 5, 50 has prime divisors of 2 and 5, so they have the same prime divisors. 15 has prime divisors of 3 and 5, and 12 has prime divisors of 3 and 2, so they have different prime divisors. I wrote some solution for that and tried to find some better way of solving the task. While googling I found one solution which relies on a claim that Greatest Common Divisor of 2 numbers 'contains' all of their common prime divisors.
I tried to think of proof of that claim, but wasn't able to do it. Also I wasn't able to google such a proof. I believe it should be something extremely simple, can someone point me to some sketch of a proof please?
If anyone is interested - link to a full solution I am trying to understand: http://codesays.com/2014/solution-to-common-prime-divisors-by-codility/
Proof is simple. Let g be the gcd of a and b. So we can express a and b as a=gc and b=gd. If d and c had any common prime factor p, then p*g would be the gcd, contradicting our definition of g as the gcd. QED the gcd of a,b contains ALL the common factors of a,b.