# if $p\mid a$ and $p\mid b$ then $p\mid \gcd(a,b)$

I would like to prove the following property :

$$\forall (p,a,b)\in\mathbb{Z}^{3} \quad p\mid a \mbox{ and } p\mid b \implies p\mid \gcd(a,b)$$

Knowing that :

## Definition

Given two natural numbers $a$ and $b$, not both zero, their greatest common divisor is the largest divisor of $a$ and $b$.

• If $\operatorname{Div}(a)$ denotes the set of divisors of $a$, the greatest common divisor of $a$ and $b$ is $\gcd(a,b)=\max(\operatorname{Div}(a)\cap\operatorname{Div}(b))$
• $$d=\operatorname{gcd}(a,b)\iff \begin{cases}d\in \operatorname{Div}(a)\cap\operatorname{Div}(b) & \\ & \\ \forall x \in \operatorname{Div}(a)\cap\operatorname{Div}(b): x\leq d \end{cases}$$
• $$\forall (a,b) \in \mathbb{N}^{2}\quad a\mid b \iff Div(a) \subset Div(b)$$
• $$\forall x\in \mathbb{Z}\quad \operatorname{Div}(x)=\operatorname{Div}(-x)$$
• If $a,b\in\mathbb{Z}$, then $\gcd(a,b)=\gcd(|a|,|b|)$, adding $\gcd(0,0)=0$

Indeed,

Let $(p,a,b)\in\mathbb{Z}^{3}$ such that $p\mid a$ and $p\mid b$ then :

$p\mid a \iff \operatorname{Div}(p)\subset \operatorname{Div}(a)$ and $p\mid b \iff \operatorname{Div}(p)\subset \operatorname{Div}(b)$ then

$\operatorname{Div}(p)\subset \left( \operatorname{Div}(a)\cap \operatorname{Div}(b)\right) \iff p\mid \gcd(a,b)$

Am I right?

• @ yes of cours in the context of divisibility – Educ May 4 '16 at 14:30
• What is $capDiv$? – TheRandomGuy May 4 '16 at 14:55
• As far as I believe, your proof is perfectly fine but you must mention beforehand that the $Div$ function gets a set of the prime divisors of a number. – TheRandomGuy May 4 '16 at 14:58
• If you already know $\operatorname{Div}(\gcd(a,b))=\operatorname{Div}(a)\cap\operatorname{Div}(b)$ you have nothing to prove. – egreg May 4 '16 at 16:35
• yes so i will remove it – Educ May 4 '16 at 16:54

It depends on what definition of greatest common divisor you use. You probably use the second one.

## Definition 1

Given natural numbers $a$ and $b$, the natural number $d$ is their greatest common divisor if

1. $d\mid a$ and $d\mid b$
2. for all $c$, if $c\mid a$ and $c\mid b$, then $c\mid d$

Theorem. The greatest common divisor exists and is unique.

Proof. Euclidean algorithm.

## Definition 2

Given two natural numbers $a$ and $b$, not both zero, their greatest common divisor is the largest divisor of $a$ and $b$.

If $\operatorname{Div}(a)$ denotes the set of divisors of $a$, the greatest common divisor of $a$ and $b$ is $\gcd(a,b)=\max(\operatorname{Div}(a)\cap\operatorname{Div}(b))$

## Extension to $\mathbb{Z}$, for both definitions

If $a,b\in\mathbb{Z}$, then $\gcd(a,b)=\gcd(|a|,|b|)$, adding $\gcd(0,0)=0$ for definition 2.

## Proof of the statement using definition 1

With this definition, the statement is obvious.

## Proof of the statement using definition 2

Let $p\mid a$ and $p\mid b$. We need to show that $p\mid\gcd(a,b)$. It is not restrictive to assume $p,a,b>0$.

It is true that $\operatorname{Div}(p)\subseteq\operatorname{Div}(a)\cap\operatorname{Div}(b)$, but this just implies that $p\le\gcd(a,b)$, not that it is a divisor thereof.

The proof can be accomplished by using the fact that $\gcd(a,b)=ax+by$ for some integers $x$ and $y$ (Bézout's theorem). With this it is easy: $a=pr$, $b=ps$, so $$\gcd(a,b)=ax+by=prx+psy=p(rx+sy)$$

How to prove Bézout's theorem is beyond the scope of this answer.

• Yeah thank you this is great explanation but note that $$\forall (a,b) \in \mathbb{N}^{2}\quad a\mid b \iff Div(a) \subset Div(b)$$ – Educ May 4 '16 at 15:20
• @Educ Yes, but you have an intersection to cope with and you didn't prove that $\operatorname{Div}(\gcd(a,b))=\operatorname{Div}(a)\cap\operatorname{Div}(b)$ (which is precisely the statement you want to prove). – egreg May 4 '16 at 15:21
• $\operatorname{Div}(\gcd(a,b))=\operatorname{Div}(a)\cap\operatorname{Div}(b)$ this can be proven by en.wikipedia.org/wiki/Euclidean_algorithm – Educ May 4 '16 at 15:30
• @Educ Yes, of course; but you have to state what you have available. As it stands, your proof is not sufficient. – egreg May 4 '16 at 15:32
• alright i will edit my question to state what i have available – Educ May 4 '16 at 15:33

One line proof using ring theory: $$(a) \subset (p), (b) \subset (p) \implies (a,b) \subset (p)$$. $$\mathbb{Z}$$ is PID implies $$(a,b)$$ is principal. We are done.

One alternative is:

By Bezout's Lemma, we know that for all $$(a, b)$$, $$\exists x, y \in \mathbb{Z}. ax + by = \gcd(a, b)$$.

So we have to prove that:

$$p|ax+by$$

Since, $$p|a \implies a = pk_1$$ and $$p|b \implies b = pk_2$$ for $$k_1, k_2 \in \mathbb{Z}^+$$.

$$\implies p|pk_1x + pk_2y$$ $$\implies p|p(k_1x + k_2y)$$ which is true.

• Thank you but what about my proof – Educ May 4 '16 at 14:52
• @Educ As far as I believe, your proof is perfectly fine but you must mention beforehand that the $Div$ function gets a set of the prime divisors of a number. – TheRandomGuy May 4 '16 at 14:58
• Why the downvote? – TheRandomGuy May 6 '16 at 5:03
• Possible correction, when you write " $\exists x, y \in \mathbb{Z}^+$ ", I believe it is not necessary for $x,y$ to be positive, so it should be $\exists x, y \in \mathbb{Z}$. For example we know $\gcd(4,10) = 2$ but there is no way $4x + 10y$ can equal to $2$ if we insist that $x, y$ are positive. – john Sep 8 '20 at 1:44