Problem of the Month
Solution to Problem 0: Equations in the integers

Several times throughout this solution, we will use the following fact: if \(\gcd(m,n)=1\) and \(km\) is a multiple of \(n\), then \(k\) is a multiple of \(n\). You might want to think about why this is true before reading the solution.

1. Suppose \(x\) and \(y\) are integers such that \(5x+8y=120\). Rearranging \(5x+8y=120\), we have that \(5x=120-8y\), and after factoring \(8\) out of the right side, we get \(5x=8(15-y)\). This means \(5x\) is a multiple of \(8\). Using the fact given before the solution and the fact that \(\gcd(5,8)=1\), we get that \(x\) is a multiple of \(8\). Similarly, \(8y=120-5x=5(24-x)\), so \(y\) is a multiple of \(5\).

   Now suppose \(x\) and \(y\) are non-negative integers such that \(5x+8y=120\). By the previous paragraph, there are integers \(X\geq 0\) and \(Y\geq 0\) such that \(x=8X\) and \(y=5Y\), which means \(5(8X)+8(5Y)=120\). Dividing by \(40\), we get \(X+Y=3\). Since \(X\) and \(Y\) are non-negative integers, \((X,Y)\) must be one of the four pairs \((0,3)\), \((1,2)\), \((2,1)\), and \((3,0)\).

   Since \(x=8X\) and \(y=5Y\), this means the only possible non-negative solutions are \[\begin{align*} x &= 0 & x &= 8 & x &= 16 & x &= 24 \\ y &= 15 & y &= 10 & y &= 5 & y &= 0\end{align*}\] It is easy to check that each of these pairs is indeed a non-negative solution to \(5x+8y=120\).

2. Observe the following: \[\begin{align*} 5(4)+8(1) &= 28 \\ 5(1)+8(3) &= 29 \\ 5(6)+8(0) &= 30 \\ 5(3)+8(2) &= 31 \\ 5(0)+8(4) &= 32 \\\end{align*}\] which shows that \(5x+8y=c\) has a non-negative solution when \(c=28\), \(c=29\), \(c=30\), \(c=31\), and \(c=32\).

   Next, observe that if \(5x+8y=c\) has a non-negative solution \((x,y)=(u,v)\), then \[\begin{align*} 5(u+1)+8v &= 5u+8v+5 \\ & = c+5,\end{align*}\] so \(5x+8y=c+5\) has a non-negative solution, namely \((x,y)=(u+1,v)\). Since \(5x+8y=28\) has a non-negative solution, so does \(5x+8y=28+5=33\). Since \(5x+8y=29\) has a non-negative solution, so does \(5x+8y=29+5=34\). Continuing in this way, we get that \(5x+8y=c\) has a non-negative solution for \(c=33\), \(c=34\), \(c=35\), \(c=36\), and \(c=37\). This process can be repeated to get that \(5x+8y=c\) has a non-negative solution for all \(c\geq 28\). It was important that we started with five consecutive values of \(c\) for which \(5x+8y=c\) has a non-negative solution.

   To finish the solution to this part, we will argue that \(5x+8y=27\) has no non-negative solution. Together with the fact that \(5x+8y=c\) has a non-negative solution for every \(c\geq 28\), this will show that the answer to the question is \(c=27\).

   Suppose \(5x+8y=27\) for non-negative integers \(x\) and \(y\). Rearranging, we have \(8y=27-5x\). Since \(x\) is a non-negative integer, \(27-5x\) has a units digit of either \(7\) or \(2\). However, \(27-5x\) must be a non-negative multiple of \(8\) since it is equal to \(8y\). There are no multiples of \(8\) with a units digit of \(7\), and the smallest nonnegative multiple of \(8\) with a units digit of \(2\) is \(32\). Therefore, \(27-5x\) cannot be a non-negative multiple of \(8\) if \(x\) is a non-negative integer, so there are no non-negative solutions to \(5x+8y=27\).

Before moving on to the solutions to Questions \(3\), \(4\), and \(5\), we will state two facts that will come up in their solutions. The proofs of these facts can be found at the end of this document.

Fact 1: Suppose \(a\) and \(b\) are positive integers with \(\gcd(a,b)=1\). For every integer \(c\), the equation \(ax+by=c\) has an integer solution.

Fact 2: Suppose \(a\) and \(b\) are positive integers with \(\gcd(a,b)=1\), that \(c\) is an integer, and that \((x,y)=(u,v)\) is an integer solution to \(ax+by=c\) (which must exist by Fact 1). For every integer \(k\), the pair \((u+bk,v-ak)\) is a solution to \(ax+by=c\). In addition, this gives every integer solution to \(ax+by=c\).

Fact 2 says that finding all integer solutions to \(ax+by=c\) comes down to finding one integer solution.

3. In Question \(2\), we saw that when \(a=5\) and \(b=8\), the answer is \(c=27\). It may take some experimentation to guess a pattern. For example, if \(a=4\) and \(b=3\), you will find that \(c=5\) is the smallest positive integer for which \(ax+by=c\) has no non-negative solution. For another example, if \(a=6\) and \(b=7\), then \(c=29\) is the largest positive integer for which \(ax+by=c\) has no non-negative solution. Even now, it might be tricky to notice a pattern. If \(1\) is added to each of these largest values of \(c\), one gets \(28\) for \(a=5\) and \(b=8\), \(6\) for \(a=4\) and \(b=3\), and \(30\) for \(a=6\) and \(b=7\). These integers factor as \(28=4\times7\), \(6=3\times 2\), and \(30=5\times 6\). With such an observation, you might guess that the largest integer \(c\) for which there are no non-negative solutions to \(ax+by=c\) is \((a-1)(b-1)-1=ab-a-b\). This would be a correct guess, and we will now prove it!

   We will prove two statements.

   • If \(a\) and \(b\) are positive integers with \(\gcd(a,b)=1\) and \(ax+by=c\) has no non-negative solution, then \(c\leq ab-a-b\).

   • If \(a\) and \(b\) are positive integers with \(\gcd(a,b)=1\), then \(ax+by=ab-a-b\) has no non-negative solution.

   The first bullet point implies that if \(c>ab-a-b\), then \(ax+by=c\) does have a non-negative solution. Therefore, the two statements above combine to imply that the answer to the question is \(c=ab-a-b\).

   Assume that \(c\) is a positive integer such that \(ax+by=c\) has no non-negative solution. We can rearrange \(ax+by=c\) to \(y=-\dfrac{a}{b}x+\dfrac{c}{b}\). This is the equation of a line with negative slope and a positive \(y\)-intercept. Furthermore, the solutions to \(ax+by=c\) are exactly the lattice points that lie on the line [A lattice point is a point in the plane whose coordinates are both integers.]. By Fact 2, the integer solutions to \(ax+by=c\), which are the lattice points on the line, are exactly the ordered pairs of the form \((u+bk,v-ak)\) where \((x,y)=(u,v)\) is any fixed integer solution and \(k\) takes every integer value. This means there are infinitely many lattice points on the line and that their \(x\)-coordinates occur at \(x=u\) and every integer multiple of \(b\) to the right and left of \(u\). Likewise, their \(y\)-coordinates occur at \(v\) and every integer multiple of \(a\) above and below \(v\).

   Thus, there must be a solution \((x,y)=(u,v)\) with the property that \(u < 0\) but \(u+b\geq0\). We will fix the solution \((x,y)=(u,v)\) to be the lattice point on the line \(y=-\dfrac{a}{b}x+\dfrac{c}{b}\)

   that is closest to the \(y\)-axis among those with a negative \(x\)-coordinate. Since \(u < 0\) and \(u\) is an integer, it must be that \(u\leq -1\). The diagram below depicts the line \(y=-\dfrac{a}{b}x+\dfrac{c}{b}\) as well as the lattice point \((u,v)\), and the next lattice point on the line moving from \((u,v)\) to the right. We are assuming there are no non-negative solutions, which means the next lattice point cannot be in the first quadrant. However, it has a positive \(x\)-coordinate by the assumption on \((u,v)\), so it must appear below the \(x\)-axis in order to fail to be a non-negative solution.

   

   The next lattice point on the line moving to the right from \((u,v)\) is \((u+b,v-a)\). As mentioned above, it must be in the fourth quadrant, which means \(v-a<0\). Since \(v\) and \(a\) are both integers, so is \(v-a\), which means \(v-a\leq -1\) which can be rearranged to \(v\leq a-1\).

   We now have that \(au+bv=c\) as well as \(u\leq -1\) and \(v\leq a-1\). Therefore, \[\begin{align*} c &= au+bv \\ &\leq a(-1)+b(a-1) \\ &= ab-a-b.\end{align*}\] Therefore, if \(ax+by=c\) has no non-negative solutions, then \(c\leq ab-a-b\), as claimed.

   For the second statement, suppose \(ax+by=ab-a-b\) for integers \(x\) and \(y\). Rearranging and factoring, we get \(a(x+1)+b(y+1)=ab\). Since both \(a(x+1)\) and \(ab\) are multiples of \(a\), it must also be the case that \(b(y+1)\) is a multiple of \(a\). We are assuming that \(\gcd(a,b)=1\), so this means \(y+1\) is a multiple of \(a\). Therefore, there is some integer \(Y\) so that \(y+1=aY\). By similar reasoning, there is an integer \(X\) such that \(x+1=bX\).

   Substituting \(y+1=aY\) and \(x+1=bX\) into \(a(x+1)+b(y+1)=ab\), we get the equation \(abX+abY=ab\), and since \(ab\) must be positive, we can divide through by it to get \(X+Y=1\). If the sum of two integers is \(1\), then one of them must be non-positive. Therefore, either \(X\leq 0\) or \(Y\leq 0\). By how \(X\) and \(Y\) are defined, this means either \(\dfrac{x+1}{b}\leq 0\) or \(\dfrac{y+1}{a}\leq 0\). Since \(a\) and \(b\) are positive, this means either \(x+1\leq 0\) or \(y+1\leq 0\), which implies that one of \(x\) and \(y\) is negative. Therefore, no integer solution to \(ax+by=ab-a-b\) can be non-negative.

   As discussed earlier, we have shown that \(ax+by=c\) has a non-negative solution for every integer \(c>ab-a-b\) and we have now shown that \(ax+by=ab-a-b\) has no non-negative solution. Therefore, \(c=ab-a-b\) is the largest integer with the property that \(ax+by=c\) has no non-negative solution.

4. We will show that for every positive integer \(n\), there are exactly \(ab\) positive integers \(c\) for which there are exactly \(n\) non-negative solutions to \(ax+by=c\).

   Suppose \(c\) has the property that there are exactly \(n\) non-negative solutions to \(ax+by=c\). Following the reasoning in the solution to 3., we are interested in lattice points on the line \(y=-\dfrac{a}{b}x+\dfrac{c}{b}\). As discussed earlier, there are infinitely many such lattice points and we can choose \((u,v)\) to be the lattice point on the line with the property that \(u<0\) and \(u+b\geq 0\). The next \(n\) lattice points on the line moving to the right are those of the form \((u+kb,v-ka)\) where \(k\) ranges over the integers from \(1\) through \(n\) inclusive.

   In order for there to be exactly \(n\) non-negative solutions, the first \(n\) lattice points on the line to the right of \((u,v)\) must be in the first quadrant. The diagram below is similar to the one in the solution to Question \(3\), but it depicts the situation for \(n=5\). The point \((u,v)\) is in the second quadrant, the next five moving along the line to the right are in the first quadrant, and the next lattice point, \((u+(n+1)b,v-(n+1)a)\), is in the fourth quadrant.

   

   For \((u+(n+1)b,v-(n+1)a)\) to be the first lattice point on the line to the right of \((u,v)\) that does not correspond to a non-negative solution, it must not be in the first quadrant while \((u+nb,v-na)\) must be in the first quadrant. Since \(k\) and \(b\) are positive, the assumptions on \((u,v)\) imply that \((u+kb,v-ka)\) has a non-negative \(x\)-coordinate for every positive integer \(k\). This means \((u+nv,v-na)\) has a non-negative \(y\)-coordinate and \((u+(n+1)b,v-(n+1)a)\) has a negative \(y\)-coordinate. This leads to the two inequalities \(v-na\geq 0\) and \(v-(n+1)a<0\).

   From our assumption about \(c\), we have deduced that there is a nonnegative solution \((u,v)\) satisfying \(u\) and \(v\) satisfying \(u<0\), \(u+b\geq 0\), \(v-na\geq 0\), and \(v-(n+1)a<0\). Since all quantities are integers, we can replace the inequality \(u<0\) with \(u\leq -1\) and replace \(v-(n+1)a<0\) with \(v-(n+1)a\leq -1\). Rearranging and combining these inequalities, we have \[\begin{align*} -b &\leq u \leq -1 \tag{1}\\ na &\leq v \leq (n+1)a-1 \tag{2}\end{align*}\] There are \(b\) integers \(u\) satisfying \((1)\) and there are \(a\) integers \(v\) satisfying \((2)\). We now have that if \(c\) is such that there are exactly \(n\) non-negative solutions to \(ax+by=c\), then there are integers \(u\) and \(v\) satisfying \((1)\) and \((2)\) respectively, as well as \(au+bv=c\).

   Next, we suppose \(u\) satisfies \((1)\) and \(v\) satisfies \((2)\) and define \(c=au+bv\). The inequalities \((1)\) and \((2)\) imply \(u<0\), \(u+b\geq 0\), \(v-na\geq 0\), and \(v-(n+1)a<0\). Following the reasoning from earlier in this part and in the solution to \(3\), this means \(ax+by=c\) has exactly \(n\) non-negative solutions. Moreover, since \(n\geq 1\), we have \[c=au+bv\geq a(-b)+b(na)\geq -ab+ab=0\] which says that \(c\) is non-negative. [It is worth remarking here that if \(n=0\), there are still are exactly \(ab\) integers \(c\) for which there are \(n\) non-negative solutions to \(ax+by=c\). However, some of those integers will be negative. With \(n\geq 1\), all of the integers \(c\) for which there are exactly \(n\) non-negative solutions to \(ax+by=c\) happen to be non-negative.]

   We have that \(ax+by=c\) has exactly \(n\) non-negative solutions exactly when \(c\) takes the form \(c=au+bv\) for some integers \(u\) satisfying \((1)\) and \(v\) satisfying \((2)\). Since there are \(b\) choices for an integer \(u\) satisfying \((1)\) and \(a\) choices for an integer \(v\) satisfying \((2)\), there are at most \(ab\) values of \(c\) that satisfy these conditions. To finish the argument, we must show that we indeed get \(ab\) distinct integers when computing \(au+bv\) for every possible choice of \(u\) satisfying \((1)\) and \(v\) satisfying \((2)\).

   To do this, we will assume that \(u_1\) and \(u_2\) both satisfy \((1)\), that \(v_1\) and \(v_2\) both satisfy \((2)\), and that \(au_1+bv_1=au_2+bv_2\) and deduce that \(u_1=u_2\) and \(v_1=v_2\). By possibly relabelling, we can assume that \(u_1\geq u_2\). With these assumptions, rearrange \(au_1+bv_1=au_2+bv_2\) to get \(a(u_1-u_2)=b(v_2-v_1)\). This means \(a(u_1-u_2)\) is a multiple of \(b\). Since \(\gcd(a,b)=1\), \(u_1-u_2\) is a multiple of \(b\). However, both \(u_1\) and \(u_2\) are between \(-b\) and \(-1\) inclusive, so their difference is smaller than \(b\). We have that \(0\leq u_1-u_2<b\) is a multiple of \(b\). The only possibility is that \(u_1-u_2=0\), or \(u_1=u_2\). This means \(b(v_1-v_2)=0\) as well, and since \(b\neq 0\), \(v_1=v_2\).

   The question asked for the answer with \(n=2025\), but we have shown that the answer is \(ab\) for every integer \(n\geq 1\), which includes \(n=2025\).

5. From the reasoning in 4., we know that the positive integers \(c\) with the property that \(ax+by=c\) has exactly \(n\) non-negative solutions are exactly the integers of the form \(au+bv=c\) where \(-b\leq u\leq -1\) and \(na\leq v\leq (n+1)a-1\).

   Observe that there are exactly \(b\) possible values of \(u\) and \(a\) possible values of \(v\), so we need to add \(ab\) integers together.

   We will do this by examining the \(u\)’s first, then the \(v\)’s. Observe that the sum contains exactly \(a\) copies of \(au\) for every \(u\) satisfying \(-b\leq u\leq -1\). Therefore, the "\(u\) part" of the sum is \[\begin{align*} & a(-a-2a-3a-4a-\cdots-(b-1)a-ba) \\ &= -a^2(1+2+3+\cdots+(b-1)+b) \\ &= -\frac{a^2b(b+1)}{2}.\end{align*}\] By similar reasoning, the sum contains exactly \(b\) copies of the term \(bv\) for every \(v\) satisfying \(na\leq v\leq (n+1)a-1=na+a-1\). This means the "\(v\) part" of the sum is \[\begin{align*} & b\big(bna+b(na+1)+b(na+2)+\cdots+b(na+a-2)+b(na+a-1)\big) \\ &= b^2\big(na+(na+1)+(na+2)+\cdots+(na+a-2)+(na+a-1)\big) \\ &=b^2\big(a(na)+1+2+3+\cdots+(a-2)+(a-1)\big) \\ &= a^2b^2n+b^2(1+2+3+\cdots+(a-2)+(a-1)) \\ &=a^2b^2n+\frac{b^2(a-1)a}{2}\end{align*}\] Therefore, the sum we seek is \[\begin{align*} a^2b^2n+\frac{b^2(a-1)a}{2} - \frac{a^2b(b+1)}{2} &= \dfrac{ab}{2}\left(2abn+b(a-1)-a(b+1)\right) \\ &= \dfrac{ab}{2}\left(2abn+ab-b-ab-a\right) \\ &= \dfrac{ab}{2}\left(2abn-a-b\right).\end{align*}\]

As promised, we now include proofs of Fact 1 and Fact 2, which were stated between the solutions to Questions 2 and 3. The proof of Fact 1 makes use of the fact that if \(\gcd(a,b)=1\), then \(ax+by=1\) always has an integer solution. This is a well known fact from number theory that you may wish to look up.

Fact 1: Suppose \(a\) and \(b\) are positive integers with \(\gcd(a,b)=1\). For every integer \(c\), the equation \(ax+by=c\) has an integer solution.

Fact 2: Suppose \(a\) and \(b\) are positive integers with \(\gcd(a,b)=1\), that \(c\) is an integer, and that \((x,y)=(u,v)\) is an integer solution to \(ax+by=c\) (which must exist by Fact 1). For every integer \(k\), the pair \((u+bk,v-ak)\) is a solution to \(ax+by=c\). In addition, this gives every integer solution to \(ax+by=c\).