Answer: 39
==============================================
Explanation:
Let n be the number we want to find. We want n to be as small as possible, but also be a positive integer. Intuitively, we can see that n cannot be smaller than 16; otherwise, we don't meet the remainder requirements.
Divide n over 12 and we get some quotient x and remainder 3
So,
n/12 = (quotient) + (remainder)/12
n/12 = x + 3/12
Multiply both sides by 12 to end up with
n = 12x + 3
Similarly, if we divide over 16 we get some other quotient y and remainder 7
n/16 = y + 7/16
which turns into
n = 16y + 7
after multiplying both sides by 16
-----------
We have these two equations
Apply substitution and do a bit of rearranging like so
12x+3 = 16y+7
12x-16y = 7-3
4(3x-4y) = 4
3x-4y = 4/4
3x-4y = 1
The goal from here is to find the smallest positive integers x and y that make that equation true. We have a few options here and they are
- Guess and check: We have a small sample size to work with so it shouldn't take too long. Make a table of xy values where you have x along the top row and y along the left column. Then plug each x,y pair into the equation above to see if you get a true statement or not. Again, keep in mind that x and y are positive integers.
- Graphing: Graph the line 3x-4y = 1, which is the same as y = (3/4)x - 1/4 and note where the line lands on a lattice point. Focus on the upper right quadrant of the graph. This quadrant is above the x axis and to the right of the y axis.
- Extended Euclidean Algorithm: This method is the most efficient, but it's only useful if your teacher has gone over it.
Whichever method you use, you should find that (x,y) = (3,2) is the point we want.
Note how:
3x-4y = 1
3(3)-4(2) = 1
9-8 = 1
1 = 1
So that verifies (3,2) is on the line 3x-4y = 1.
Because x = 3 and y = 2, we know that
n = 12x + 3
n = 12*3 + 3
n = 39
and we can see that
n = 16y + 7
n = 16*2 + 7
n = 39
So 39 is the smallest such integer such that when we divide it over 12 and 16, we get remainders 3 and 7 respectively.
Here's a quick verification that we've fit the requirements.
39/12 = 3 remainder 3
39/16 = 2 remainder 7
We know we hit the smallest value of n because (x,y) was made to be the smallest positive integer solution to 3x-4y = 1. There are infinitely many positive integer (x,y) solutions to 3x-4y = 1, which in turn means there are infinitely many numbers n that satisfy the remainder conditions (but n is not the smallest possible in those cases).
