3
$\begingroup$

I have to demonstrate this three formulae:

  1. $\gcd(ac,bc)=c\gcd(a,b), \forall a,b,c \in \mathbb{N}$
  2. $a\mid c \land b\mid c \land \gcd(a,b)=1 \implies ab\mid c$
  3. $\gcd(a,b,c)=xa+yb+zc, \forall a,b,c,x,y,z \in \mathbb{Z}$

and I have no idea to get started using the definition of GCD ($\gcd=\max(k\in \mathbb{N} : k\mid ac\land k\mid bc)$) or other things.

Could you help me please?

  • 1
    One way to prove two positive integers are equal is to prove that the are divisors of each other. I suspect you'll find that useful in some of this.2012-07-10
  • 2
    3. is not correct. The gcd(a,b,c) is the least positive value of the right hand side. This property of gcd you can use to prove 1.2012-07-10
  • 2
    3.should be this $\gcd(a,b,c)=xa+yb+zc, \forall a,b,c \quad \exists x,y,z \in \mathbb{Z}$2012-07-10
  • 0
    @SaurabhHota : I'd write it as $\Big(\gcd(a,b,c)=xa+yb+zc,\ ∀a,b,c\Big)\ ∃x,y,z∈Z$, to be clear that the way in which the quantifiers are nested matters.2012-07-10

2 Answers 2