Results 1 to 2 of 2

Thread: [SOLVED] Greatest Common Divisor Problems

  1. #1
    Member
    Joined
    Mar 2008
    From
    Acolman, Mexico
    Posts
    118

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


    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    $\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$)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Common Divisor of (9m+8, 6m+5)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 15th 2011, 05:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Oct 25th 2010, 05:45 AM
  3. Greatest common divisor
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Apr 18th 2010, 03:16 PM
  4. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 17th 2009, 07:16 PM
  5. [SOLVED] Greatest Common Divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 26th 2009, 03:00 PM

Search Tags


/mathhelpforum @mathhelpforum