# GCD using quantifiers - where did I make a mistke?

So I had a task "Formulate a statement d=GCD(a,b,c) using quantifiers" on my exam which was marked as wrong - however, I don't know why is that wrong so could anybody please help me understand? I formulated it as:

$\exists_{d}\forall_{k}(((k|a)\land(k|b)\land(k|c))\Rightarrow d\geq k)$

I had the first term ($\exists_{d}$) marked as wrong. Why is that so?

-

You forgot to say that $d$ divides $a,b,c$, but let's assume you put that in. The problem is that the statement you are asked to formulate says that some specific $d$ is the gcd of some specific triple $a,b,c$. So the $\exists d$ shouldn't be there. Your statement is trying to say "$a,b,c$ has a gcd", but it should say "$d$ is the gcd of $a,b,c$".

-
Oh, I see. Thank you a lot. But how can I use the quantifiers to show such a statement? I mean: I can't just do $d=$ and write down all the rest so how should one do it? Also, thank you a lot for the disclaimer about d dividing a,b,c - shamefully, I don't remember if I wrote that down or not :) – George Shack Nov 23 '12 at 10:30
The only quantifier you need is for $k$. You don't have one for $a,b,c$ after all. Do you see how to do it now? – m_t_ Nov 23 '12 at 10:31
Hm... So something like $d=\forall_{k}(...)$? It doesn't look right to me but I never did quantifier-things with an equal sign between so maybe it's right... Is it? – George Shack Nov 23 '12 at 10:35
No, this is a type error! Martini has it right. – m_t_ Nov 23 '12 at 10:38
Yep, I see it now, it's senseless to assign some true-false value to d here, thank you :) – George Shack Nov 23 '12 at 10:39

To answer your question in the comment to @mt_'s answer. First say that $d$ divides $a$, $b$ and $c$: $$(d \mid a) \land (d \mid b) \land (d \mid c)$$ Then add your statement but without the existential quantifier: $$\forall k. \bigl((k \mid a )\land (k \mid b) \land (k \mid c) \bigr)\to k \le d$$ So you get $$(d \mid a) \land (d \mid b) \land (d \mid c) \land \forall k. \bigl((k \mid a )\land (k \mid b) \land (k \mid c) \bigr)\to k \le d$$

-
Ooh, I see. Thank you a lot :) – George Shack Nov 23 '12 at 10:37