5
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ @ yes of cours in the context of divisibility $\endgroup$
    – Educ
    May 4, 2016 at 14:30
  • $\begingroup$ What is $capDiv$? $\endgroup$ May 4, 2016 at 14:55
  • 1
    $\begingroup$ 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. $\endgroup$ May 4, 2016 at 14:58
  • $\begingroup$ If you already know $\operatorname{Div}(\gcd(a,b))=\operatorname{Div}(a)\cap\operatorname{Div}(b)$ you have nothing to prove. $\endgroup$
    – egreg
    May 4, 2016 at 16:35
  • $\begingroup$ yes so i will remove it $\endgroup$
    – Educ
    May 4, 2016 at 16:54

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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) $$ $\endgroup$
    – Educ
    May 4, 2016 at 15:20
  • $\begingroup$ @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). $\endgroup$
    – egreg
    May 4, 2016 at 15:21
  • $\begingroup$ $\operatorname{Div}(\gcd(a,b))=\operatorname{Div}(a)\cap\operatorname{Div}(b)$ this can be proven by en.wikipedia.org/wiki/Euclidean_algorithm $\endgroup$
    – Educ
    May 4, 2016 at 15:30
  • $\begingroup$ @Educ Yes, of course; but you have to state what you have available. As it stands, your proof is not sufficient. $\endgroup$
    – egreg
    May 4, 2016 at 15:32
  • $\begingroup$ alright i will edit my question to state what i have available $\endgroup$
    – Educ
    May 4, 2016 at 15:33
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you but what about my proof $\endgroup$
    – Educ
    May 4, 2016 at 14:52
  • 1
    $\begingroup$ @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. $\endgroup$ May 4, 2016 at 14:58
  • $\begingroup$ Why the downvote? $\endgroup$ May 6, 2016 at 5:03
  • $\begingroup$ 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. $\endgroup$
    – john
    Sep 8, 2020 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.