# Using only logical symbols and “$+, \cdot$” translate into a first-order logic: “$c$ is not the greatest common factor of $a$ and $b$”.

Using only logical symbols and "$+, \cdot$" translate into a first-order logic: "$c$ is not the greatest common factor of $a$ and $b$". Assume that all variables are positive integers.

I have attempted to solve this but I am not sure if my reasoning is good. Neither am I sure whether I am not lacking quantifiers.
$$\neg((\exists\alpha)(\exists\beta)(a= \alpha c\land b= \beta c) \land (\forall d)((\exists \gamma)(\exists\delta)(a=\gamma d\land b= \delta d) \Rightarrow d \le c))$$
What do you think of my solution?

• General comment. If you write your logic out in English first you're more likely to get it right and it will be easier for folks here to check. Start with "$c$ is the gcd if it divides $a$ and $b$ and ...", convert to formalism, and negate. – Ethan Bolker Nov 27 '17 at 20:00

Looks good, but I agree with Clive that you'll need to capture the $\le$ using symbols you are allowed to use. But to avoid using a $1$ as well, I propose:
$$d \le c \Leftrightarrow (d =c \lor \exists x \ d +x = c)$$
That looks pretty much correct, except that you've used the symbol $\le$, which is not a logical symbol and is not $+$ or $\cdot$. However, you can express $d \le c$ using only $+$, $\cdot$ and logical symbol by observing that $$d \le c \quad \Leftrightarrow \quad (\exists k)(c+1=d+k)$$