# 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 $\displaystyle a,b \in \mathbb{Z}$. Prove that $\displaystyle gcd(a,b)=1$ if and only if there exists $\displaystyle s,t \in \mathbb{Z}$ such that $\displaystyle as+bt=1$.

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

2. $\displaystyle gcd(a,b)=1\Rightarrow\ \text{the ideal}\ <a,b>=\mathbb{Z} \Rightarrow \exists s,t\in\mathbb{Z},\ as+bt=1$ $\displaystyle \Rightarrow(\forall c\in\mathbb{Z},\ c|a\ \text{and}\ c|b \Rightarrow c|1)\Rightarrow gcd(a,b)=1$
Let $\displaystyle p$ be a prime divisor of $\displaystyle d$. Since $\displaystyle d|ab,\ p$ has to divise $\displaystyle a$ or $\displaystyle b$ (because $\displaystyle p$ is irreducible).
But $\displaystyle gcd(d,a)=1\Rightarrow p$ doesn't divide $\displaystyle a.$ Hence $\displaystyle p|b,$ and that is true for any prime divisor of $\displaystyle d.$
Therefore $\displaystyle d|b.$ (Be more precise than me to show that $\displaystyle \forall m\in\mathbb{N},\ p^m|d\Rightarrow p^m|b$)