2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Over the integers? $\endgroup$ – Rodrigo de Azevedo Dec 22 '16 at 8:08
  • $\begingroup$ If it is over the set of integers, won't there be an exact number of solutions? $\endgroup$ – Qwerty Dec 22 '16 at 8:09
  • $\begingroup$ Do you mean nonnegative integers? $\endgroup$ – Rodrigo de Azevedo Dec 22 '16 at 8:14
  • $\begingroup$ yes its over the integers. Forgot to mention $\endgroup$ – Mayank Mittal Dec 22 '16 at 8:15
  • $\begingroup$ final edit done $\endgroup$ – Mayank Mittal Dec 22 '16 at 8:18
5
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

$$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)?$

$\endgroup$
0
$\begingroup$

$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.

$\endgroup$

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.