Next year, I'll be attending the IMO and although I've done many math contests over the years, most of the questions wanted numerical answers and the ones that required a proof were basic and simple so I'm not really used to formal proof writing; in fact in math class, my teacher always tells me that I do a lot of the steps in my head and although she knows that I know how to prove something, I can't simply do some of the steps in my head.


Prove for integers numbers $a_1, a_2,..., a_n$, there are integers $x_1, x_2, ..., x_n$ that satisfy $a_1x_1 + a_2x_2 + ... + a_nx_n = d$ where $d = gcd(a_1,a_2,...,a_n)$.

My proof:

Assume this is true for all the natural numbers less than $n$ and now we'd like to prove it for $n$(here, I just assume the reader knows Bezout's Identity).Let $d' = gcd(a_1,a_2,...,a_{n-1})$ so we have $d = gcd(d', a_n)$. There are integers(for example, this is one of the parts she says i do in my head) $y_1, y_2,...,y_{n-1}$ such that $a_1y_1+a_2y_2+...+a_{n-1}y_{n-1} = d'$. We also know there are integers $x,y$ such that $d'x + a_ny = d$(again, this is another one of those instances).

Now, I've been trying to stop myself from doing this but it got me thinking, to what extent should I prove something? What I mean is, what should I assume the person who's reviewing my proof knows? Is it just basic arithmetics? Properties of certain things such as GCD and LCM? Basic properties such as $gcd(a,b) = gcd(a, c) = 1$ iff $gcd(a,bc) = 1$? I know this might be too broad but I'm just asking for proofs in number theory and not geometry, algebra, etc.

P.S: If you think this question doesn't feet the criteria of math.se, what's an appropriate place to post this question?

Thank you so much in advance!

  • 1
    $\begingroup$ Congratulations on attending the IMO. $\endgroup$ – Cheerful Parsnip Aug 22 '19 at 17:02
  • $\begingroup$ @CheerfulParsnip Thank you so much:) $\endgroup$ – Borna Ahmadzade Aug 22 '19 at 17:17

If I were grading this proof, the questions I would have are:

  1. It looks like you are proceeding by induction. Have you established the base case?
  2. How do you know $d=\text{gcd}(d', a_n)$?

Note, I am not concerned about the existence of $y_1,\dots,y_{n-1}$, since that follows from the induction hypothesis.

  1. How do you know such $x$ and $y$ exist? (This is the same as establishing the base case for the induction.)

It's not so much a matter of what the reader knows but rather what you are able to justify. Given that the whole point of the problem is showing that the GCD of a bunch of numbers can be written as an integer combination of those numbers, you should definitely justify that for the case $n=2$, and not just assume it.

  • $\begingroup$ Yes that's exactly what my teacher says. I do these steps in my head: $(a_1,a_2,...,a_n) = ((a_1,a_2,...,a_{n-1}),a_n)$, for the basis of the induction, I'm using Bezout's Identity and the existence of such $x$ and $y$ is, again, because of the induction hypothesis where $n = 2$. $\endgroup$ – Borna Ahmadzade Aug 22 '19 at 16:49
  • $\begingroup$ @BornaAhmadzade As this answer says, you need to prove a base case. If the base case is $n=1$ then you cannot use $n=2$ as an “induction hypothesis.” If the base case is $n=2$ then it’s a base case and again not a hypothesis. $\endgroup$ – David K Aug 22 '19 at 16:58
  • $\begingroup$ @BornaAhmadzade This question is asking you to prove (generalized) Bezout's Identity, so you should not use it in your proof. In particular you should prove the case $n=2$ as your base case and also use that to justify the existence of $x$ and $y$. $\endgroup$ – kccu Aug 22 '19 at 17:08
  • $\begingroup$ @kccu Well so you sort of answered my question. I always thought the existence of integers $x$ and $y$ such that $ax + by = gcd(a,b)$ is sort of like "common knowledge" in IMO so I didn't really think I needed to prove it. But if it were a whole different question whose proof involved Bezout's Identity, would I still have to prove it? $\endgroup$ – Borna Ahmadzade Aug 22 '19 at 17:15
  • $\begingroup$ @DavidK Well, for the induction, you only need $n-1$ and $2$ so I didn't think I need it for $n=1$(which is trivial in my opinion. $gcd(a) = a$) $\endgroup$ – Borna Ahmadzade Aug 22 '19 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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