Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted

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$".

share|cite|improve this answer
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 $$

share|cite|improve this answer
Ooh, I see. Thank you a lot :) – George Shack Nov 23 '12 at 10:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.