What is the number of non-negative integral solutions (x,y) to the linear equation in two variables:
n = px + qy,
where n,p,q are arbitrary constants and positive integers?
What is the largest n for given p and q such that the above linear equation has no non-negative integral solution (x,y)?
For ex,
For n=7, p=2, q=3,
7 = 2x + 3y
has 1 such solution (2,1).
For p=2, q=5,
So for n = 2x + 5y
0 solution for n=1,
1 solution (1,0) for n=2,
0 solution for n=3,
1 solution (2,0) for n=4,
1 solution (0,1) for n=5, and
for n > 5, you can see that it will always have at least one solution.
Generally by checking for all values of n starting from 1 and incrementing it by 1, if the equation has at least one solution for min(p,q) consecutive values of n, it will always have at least one solution from those values of n onwards.
So the largest n for which n = 2x + 5y has no solution is n=3.
Could these problems be solved mathematically? Are there formula to solve these? Thank you.
Let $p, q,$ and $n$ be positive integers with $\gcd(p,q)=1$.
Lets say that $(u,v)$ is a nice solution if $u$ and $v$ are non negative integers for which $pu+qv=n$.
Since $\gcd(p,q)=1$, we know that there exists integers $A$ and $B$ such that $$Ap+Bq=n \tag{1.}$$
Then there exists integers $Q$ and $x_0$ such that
$$ \left\{ \begin{array}{l} A = Qq + x_0 \\ 0 \le x_0 < q \end{array} \right. \tag{2.} $$
Let $$y_0 = B+Qp \tag{3.}$$
Then $px_0 + qy_0 = (A-Qq)p + (B+Qp)q = Ap + Bq = n$. So
$$px_0 + qy_0 = n \tag{4.}$$
It follows that all nice solutions are of the form $(x_k, y_k)_{k=0}^{N-1}$ where
$$ \left\{ \begin{array}{l} x_k = x_0 + kq \\ y_k = y_0 - kp \end{array} \right. \tag{5.}$$
where $N$ is the largest integer for which $y_{N-1} \ge 0$.
If $y_0 < 0$, then $N = 0$.
Otherwise $N = 1 + \left \lfloor \dfrac{y_0}{p} \right \rfloor$