# Solving linear equations in integers

In the recent TCS placement test, the following question was asked.  Do you know how to solve this?

### Oranges can be packed in sets of 10 oranges in box type A or 25 oranges in box type B. A carton comprising of 1000 oranges of type a and b is packed. How many different combinations are possible in the number of type A and type B boxes while organizing the oranges?

 a. 21 b. 20 c. 19 d. 18
Finding integers solutions is one of the important question that is being asked in the recent exams. We will discuss some interesting methodologies to solve them.
If a system of equations has two variables, we need atleast two equations to solve them.  But what if, we are given only one equation?
Suppose taking my date of birth, my date is multiplied by 31 and month is multiplied by 12 and given the product as 494.  Can you determine my birth date and month?
Take an equation $ax + by = k$.
This is in the format of $A + B = k$. As $k$ is constant, If $A$ increases, $B$ should decrease.  The question is, by how much?  Simple. If "$A$" reduces by "$b$" (the coefficient of y), B should increase by "$a$" (the coefficient of x) and vice versa.
For example, 5x + 3y = 100. One solution for this equation is (20, 0). Now the next solution is (23, -5), (26, - 10) .... or (17, 5), (14, 10), .....

But some times this is not that much straight forward.

Interesting Question:
By multiplying my birth date by 31 and month by 12, I got a total of 494.  Can you tell me birth date and month?
31x + 12y = 494.

Finding the first solution is not easy in this case. So we follow a special procedure:
Now certain other clues might help us to solve this questions. Here date and months cannot be negative and both are integers.
So follow a special procedure to find the answer to this questions.
$31x + 12y = 494$
$12y = 494 - 31x$
$\Rightarrow y = \dfrac{{494 - 31x}}{{12}}$
$\Rightarrow y = 41 + \dfrac{2}{{12}} - 2x - \dfrac{{7x}}{{12}}$
We now send the intezer terms to the left and assume the expression on the left side as ‘k’.
$\Rightarrow y - 41 + 2x = \dfrac{2}{{12}} - \dfrac{{7x}}{{12}}$
$\Rightarrow k = \dfrac{2}{{12}} - \dfrac{{7x}}{{12}}$
Now we use a simple trick here. We multiply both sides with an intezer so that after dividing the ‘7x’ term by 12 we have to get remainder of ‘x’.  Here we have to multiply it by 7.
$\Rightarrow 7k = \dfrac{{14}}{{12}} - \dfrac{{49x}}{{12}}$
$\Rightarrow 7k = 1 + \dfrac{2}{{12}} - 4x - \dfrac{x}{{12}}$
Again send the intezers to the left and assume it as "$m$".
$\Rightarrow m = \dfrac{{2 - x}}{{12}}$
$\Rightarrow 12m = 2 - x$
$\Rightarrow x = 2 - 12m$  - - - - - -  (1)
Now we substitute this value of x in original equation.
=> $31 (2 – 12m) + 12y = 494$
$y = 31m + 36$ - - - - - (2)
We got $\Rightarrow x = 2 - 12m$ and $y = 31m + 36$
So x, y and positive numbers. So m can take 0, -1, -2 ...
For m = 0, we get x = 2 but y = 36. But month cannot be more than 12.
For m = -1, we get x = 14, y = 5. This is a possible solution. For m = -3 we see month becomes negative.
So 14th May is the given date and month.

Solution for the TCS question: See 2nd question