[SOLVED] Greatest Common Divisor Problems

**akolman** · February 3rd 2009, 08:52 AM

Hello, I guess these problems are not supposed to be very hard, but I am confused.

1. Let $a,b \in \mathbb{Z}$ . Prove that $gcd(a,b)=1$ if and only if there exists $s,t \in \mathbb{Z}$ such that $as+bt=1$ .

2. Prove that if $a,b,d \in \mathbb{Z}$ with $d|ab$ and $gcd(a,d)=1$ , then $d|b$ .

Thanks in advance.

**clic-clac** · February 3rd 2009, 09:26 AM

$gcd(a,b)=1\Rightarrow\ \text{the ideal}\ <a,b>=\mathbb{Z} \Rightarrow \exists s,t\in\mathbb{Z},\ as+bt=1$ $\Rightarrow(\forall c\in\mathbb{Z},\ c|a\ \text{and}\ c|b \Rightarrow c|1)\Rightarrow gcd(a,b)=1$

Let $p$ be a prime divisor of $d$ . Since $d|ab,\ p$ has to divise $a$ or $b$ (because $p$ is irreducible).
But $gcd(d,a)=1\Rightarrow p$ doesn't divide $a.$ Hence $p|b,$ and that is true for any prime divisor of $d.$
Therefore $d|b.$ (Be more precise than me to show that $\forall m\in\mathbb{N},\ p^m|d\Rightarrow p^m|b$ )

Thread: [SOLVED] Greatest Common Divisor Problems

LinkBack

Thread Tools

Display

[SOLVED] Greatest Common Divisor Problems

Similar Math Help Forum Discussions

Greatest Common Divisor of (9m+8, 6m+5)

[SOLVED] Least common multiple - Greatest common divisor

Greatest common divisor

Greatest common divisor

[SOLVED] Greatest Common Divisor

Search Tags