A problem regarding a Linear Diophantine Equation

Question

A pen costs £11 , A notebook costs £13. In how many ways can you spend exactly £1000 ?

Although it is really basic number theory, I am really having a tough time understanding it . I don't need an answer, I need a thorough explanation. Any help would be appreciated.

Answer 1

You have a linear Diophantine equation. From the wikipedia page on Diophantine equations

[A linear Diophantine, $ax+by=c$] equation has a solution (where $x$ and $y$ are integers) if and only if $c$ is a multiple of the greatest common divisor of $a$ and $b$. Moreover, if ($x$, $y$) is a solution, then the other solutions have the form $(x + kv, y − ku)$, where $k$ is an arbitrary integer, and $u$ and $v$ are the quotients of $a$ and $b$ (respectively) by the greatest common divisor of $a$ and $b$.

Back to your problem, the equation you want to solve is $11x + 13y = 1000$ where x and y are the number of pens and notebooks respectively you will buy. Now the greatest common divisor of $11$ (plays the role of $a$ in the equation on Wikipedia) and $13$ (plays the role of $b$ in the equation on Wikipedia) is $1$ since they are both prime. $1000$ (plays the role of $c$ in the equation on Wikipedia) is clearly a multiple of $1$, so this equation has a solution.

Now an easy way to find one solution is through guessing. $y=\frac{1}{13}(1000-11y)$

$x=0 \rightarrow y=76.923... \notin \mathbb{Z}$

$x=1 \rightarrow y=76.077... \notin \mathbb{Z}$

$x=2 \rightarrow y=75.231... \notin \mathbb{Z}$

$x=3 \rightarrow y=74.385... \notin \mathbb{Z}$

$x=4 \rightarrow y=73.538... \notin \mathbb{Z}$

$x=5 \rightarrow y=72.692... \notin \mathbb{Z}$

$x=6 \rightarrow y=71.846... \notin \mathbb{Z}$

$\boxed{x=7 \rightarrow y=71 \in \mathbb{Z}}$

Now that we have $(x,y) = (7,71)$ as a solution, everything of the form $(7+13k,71-11k)$ is a solution. For example with $k=1$, we get $(20,60)$, which upon checking, is also a solution. You also must restrict the value of k so that $x$ and $y$ are both positive, since one cannot buy a negative quantity of an item at a store.

Answer 2

$$11x+13y=500(13-11)$$

$$\iff11(x+500)=13(500-y)$$

$\implies11$ must divide $500-y\implies y=500-11t$ where $t$ is any integer

Clearly, $500-11t\ge0\iff t\le ?$

Similarly $x=13t-500\ge0\iff t\ge?$

Answer 3

We want to find all nonnegative integer solutions for

$$11x+13y=1000.$$

First, guess one solution, e.g. $x=7, y=71$. Then generalize

$$\left\{\begin{array}{l}x=7+13k,\\y=71-11k,\end{array}\;(k\in\mathbb{Z})\right.$$

Finally, count the number of solutions. We have $k=0,1,2,\ldots,6$. So there are $7$ solutions.