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$ Aug 22 '19 at 17:02
  • $\begingroup$ @CheerfulParsnip Thank you so much:) $\endgroup$
    – user668217
    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$
    – user668217
    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$
    – user668217
    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$
    – user668217
    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