Finding the Greatest Common Divisor is achieved by running through the factors of two or more numbers and find the largest number that they all have in common. For convenience sake lets say the two number we're comparing are $ m,n$ Would it be acceptable to define GCD as: $(\forall{m,n}\in \mathbb{Z})(\exists{x}\in\mathbb{Z}) ((x|m)\land(x|n))$
I don't know if this a correct definition for, but I feel like It's on the right track.
This is incomplete. You also have to state that no larger $x$ works.
For example, $x=1$ satisfies your conditions.