If $x, y \leq 500$ then find the number of nonnegative integer solutions to $4 x - 17y = 1$

Question

If $x, y \leq 500$ then find the number of nonnegative integer solutions to $4 x - 17y = 1$.

I don't know how to proceed. Please help me out. Thank you.

Answer 1

We are asked to find integer solutions for $x,y$.

We can get particular solutions simply by plugging in values. Our first solution is obtained as: $y’ = 3$ and $x’ = 13$.

Thus, the general solution for x will be:

$$x = x’ + bn = 13 + 17n$$

Hence lower limit for $n$ is $n \geq 0$.

Now we’ll find upper limit using given restriction $x \leq 500$. Plugging in general solution we’ll get: $$13 + 17n \leq 500 \Rightarrow 17n \leq 487\Rightarrow n \leq 28$$

And our list of possible values of $n$ has following representation: $$0, 1,2, 3,\cdots 28$$ Also, we can check that for $n=28$, the value of $y$ also lies within $500$.

The total number of elements is thus $\boxed{29}$.

Answer 2

Suppose you have some pair of integers $(x_0, y_0)$ that are a solution to $y = \dfrac{4x - 1}{17}$. Then $$\dfrac{4(x_0 + 17) - 1}{17} = \frac{4x_0 + 4 \cdot 17 - 1}{17} = \dfrac{4x_0 -1}{17} + 4$$ so that $\left(x_0 + 17, y_0 + 4 \right)$ is another solution.

Can you find the "smallest" solution, and figure out how many times you can "increment" to another solution with $x, y$ in the proper bounds?

Bonus: Why do we only need to worry about incrementing $x_0$ by multiples of $17$? Why can't there be some solution $(x, y)$ where $x = x_0 + k$, with $1 \le k \le 16$?

Answer 3

$$4x-17y=17-16\iff4(x+4)=17(y+1)\iff\dfrac{17(y+1)}4=x+4$$ which is an integer

$\implies4|17(y+1)\implies4|(y+1)$

So $y$ can be written as $4m-1$ where $m$ is any integer

$\implies x=17m-4$

We need $0\le17m-4\le500\iff1\le m\le29\ \ \ \ (1)$

and $0\le4m-1\le500\iff1\le m\le125\ \ \ \ (2)$

What is the intersection of $(1),(2)?$

Answer 4

$4x-17y=1 \implies 4x=17y+1$

So we have $x,y\in \Bbb N$ and thus $x>y$, so we can solve $$4x\equiv 1 \bmod 17 $$ and then keep $x\leq 500$.

Since $17$ is prime we only expect one equivalence solution, so $4x\equiv 1\equiv 52 \implies x\equiv 13\bmod 17$ gives us the answer we need.

Then $\lfloor 500/17\rfloor=29$ and $500\equiv 7 \bmod 17$ (with $7<13$) so there are $\fbox{29}$ values of $(x,y)$ that meet the criteria. The smallest is $(13,3)$; the next is $(30,7)$ etc.