Divides[x_, y_] := Mod[y, x] == 0	(* x divides y *)

gcd[0, b_] := b  (* special cases *)
gcd[a_, 0] := a

gcd[a_, b_] :=
	Module[{c},
		c = Min[a, b];
		While[ !(Divides[c, a] && Divides[c, b]), c-- ];
		c
	]
