GCD and LCM with logical symbols

Question

I got one question which says;

Write a formula corresponding to: 1. “a is the greatest common divisor of b and c” 2. “a is the least common multiple of b and c” Use logical symbols, brackets, · and =. Any other symbols need to be defined.

it seems easy but can someone help me with that ?

Answer 1

Do it in steps:

1. "$a$ is a divisor of $b$": $\exists k_1\;a\cdot k_1 = b$.
2. "$a$ is a divisor of $c$": $\exists k_2\;a\cdot k_2 = c$.
3. "$a$ is a common divisor of $b$ and $c$": $(\exists k_1\;a\cdot k_1 = b) \land (\exists k_2\;a\cdot k_2 = c)$.
4. "$a$ is the greatest integer satisfying $P(a)$": $P(a) \land (\forall x\;P(x) \implies x \le a)$.

Substituting the third step into the fourth, we get $$(\exists k_1\;a\cdot k_1 = b) \land (\exists k_2\;a\cdot k_2 = c) \land (\forall x\;((\exists k_1\;x\cdot k_1 = b) \land (\exists k_2\;x\cdot k_2 = c)) \implies x \le a)$$ which represents "$a$ is the greatest common divisor of $b$ and $c$".

There are variations on each of these steps, variations in the notation, and you might be working with a different set of primitives allowed, so you should adjust this to your own needs. For example, if you're not allowed $\le$, then you should proceed from step 3 to trying to write a statement like

5. "$a$ is a common divisor of $b$ and $c$, and if $x$ is a common divisor of $b$ and $c$, then $x$ divides $a$"

which is an equivalent characterization of GCD.

Writing up LCM is more or less the same, except you stand on your head while you do it.

Answer 2

I don't know what language you are talking about, but here is a little something I wrote up out of boredom. Hope it helps!

Let $a|b$ mean "$a$ divides $b$", let $\geq$ mean "greater than or equal to.

$a |b \wedge a|c \wedge \forall y (y |b \wedge y|c \rightarrow a\geq y))$

"$a$ divides $b$, $a$ divides $c$, and for all $y$, if $y$ divides $b$ and $y$ divides $c$, then $a$ is greater than or equal to $y$"

And for the other one... let $xy=z$ mean $x$ times $y$ equals $z$ and $\leq$ mean less than or equal to.

$\exists n \exists m (bn=a \wedge cm=a) \wedge \forall y \exists x \exists z (bx=y \wedge cz=y \rightarrow a \leq y) $

"there is an $n$ and an $m$ such that $bn=a$ and $cm=a$ (in other words, $a$ is a multiple of $b$ and $c$), and for all $y$, if $y$ is a multiple of $b$ and $c$ then $a$ is less than or equal to $y$."