# Thread: [SOLVED] Greatest Common Divisor Problems

1. ## [SOLVED] Greatest Common Divisor Problems

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$.

2. $gcd(a,b)=1\Rightarrow\ \text{the ideal}\ =\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$)