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$
  • $\begingroup$ @ yes of cours in the context of divisibility $\endgroup$ – Educ May 4 '16 at 14:30
  • $\begingroup$ What is $capDiv$? $\endgroup$ – TheRandomGuy May 4 '16 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$ – TheRandomGuy May 4 '16 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 '16 at 16:35
  • $\begingroup$ yes so i will remove it $\endgroup$ – Educ May 4 '16 at 16:54
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$
  • $\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 '16 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 '16 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 '16 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 '16 at 15:32
  • $\begingroup$ alright i will edit my question to state what i have available $\endgroup$ – Educ May 4 '16 at 15:33
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$
  • $\begingroup$ Thank you but what about my proof $\endgroup$ – Educ May 4 '16 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$ – TheRandomGuy May 4 '16 at 14:58
  • $\begingroup$ Why the downvote? $\endgroup$ – TheRandomGuy May 6 '16 at 5:03
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$

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.