0
$\begingroup$

For $a,b$ in the natural numbers. How do I prove that $x$ divides $a$ and $x$ divides $b$ iff $x$ divides $\gcd(a,b)$.

Please no proofs using theorems.

$\endgroup$
0
$\begingroup$

$x|a $. let $a=a'x $. Let $d=\gcd (a,b) $. Let $a=Ad=a'x $. By unique factorization we can "break" this up to $a =(A)(d)=(A'x')(d'x")=(A'd')(x'x")=a'x$.

In other words $A'$ is a common factor of $A$ and $a'$, $x'$ is a common factor of $A $ and $x $, etc.

$x|b $. Let $b=b'x $. Let $b=Bd=b'x $.

So $b=B (d'x")=b'(x'x")$. By unique factoization, we can break this to: $b=(B'x')(d'x")=(b"d')(x'x") $.

Notice $d'x'x"=x'd $ is a common factor of $a$ and $b $.

But $d$ is the greatest common divisor. So $dx'\le d$ so $x' =1$ and $x"=x $ $A'=1$ and $B'=1$.

So $a=Ad=Ad'x$ and $b=Bd=d'x$ and $d =d'x $ and $x|d=\gcd (a,b)$

====

If $x|\gcd (a,b) $ and $\gcd (a,b)|a $ then $x|a $. As $\gcd (a,b)|b $, $x|b $.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

You have to translate the word 'divide' into the language of ideals. We say that $a$ divides $b$ if $I_a \supset I_b$ (e.g. the set of multiples of $5$ contains the set of multiples of $15$). So for every common divisor $c$ of $a$ and $b$ we have $I_c \supset I_a$ and $I_c \supset I_b$ so that $I_c \supset I_a \cup I_b$. The smallest ideal that contains $I_a \cup I_b$ is $I_{\gcd(a,b)}$. This can be proved by using the property $I_{uv} = I_u \cup I_v$ and taking the intersection over all common factors of $a$ and $b$. Viewed like this what you have to prove is $I_x \supset I_a, I_x \supset I_b \iff I_x \supset I_{\gcd(a,b)}$.

Example $a = 30, b = 20 $: $I_a = \{0, 30, 60, 90, \ldots\}$, $I_b = \{0, 20, 40, 60, \ldots\}$. Then $2$ and $5$ being the common divisors of $a$ and $b$ : $I_{\gcd(a,b)} = \{0, 2, 4, 6, 8, \ldots\} \cap \{0, 5, 10, 15, 20, \ldots\} = \{0, 10, 20, 30, 40, \ldots\}$. The proposition now sounds like $I_x \supset \{0, 30, 60, 90, \ldots\}, I_x \supset \{0, 20, 40, 60, \ldots\} \iff I_x \supset \{0, 10, 20, 30, 40, \ldots\}$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Using fundamental theorem of arithmetic

$$\displaystyle a = \prod_{i=1}^{k}p_i^{\alpha_i} \,\, , \quad b = \prod_{i=1}^{k}p_i^{\beta_i}$$

We have : $\displaystyle\gcd(a,b)=\prod_{i=1}^{k}p_i^{\min(\alpha_i, \beta_i)}$

If $x | a$ and $x | b$ then $x = \displaystyle \prod_{i=1}^{k}p_i^{\gamma_i}$ , with $\forall i \in \{1,2,\cdots,k\} \,\, : \,\, \gamma_i \leq \alpha_i \text{ and } \gamma_i \leq \beta_i$

Then $\forall i \in \{1,2,\cdots,k\} \,\, : \,\, \gamma_i \leq \min(\alpha_i, \beta_i)$

Then $x$ devide $\gcd(a, b)$

And we have $\gcd(a,b)$ devide $a$ and $b$, then if $x$ devide $\gcd(a,b)$, $x$ will devide $a$ and $b$.

conclusion:

$$d = \gcd(a,b) \iff \left\{\begin{matrix}d | a \, \text{ and } \, d | b \\ x | a \, \text{et} \, x | b \implies x | d\end{matrix}\right.$$

| cite | improve this answer | |
$\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.