Q8 - Integer equation practice problem
Question: 3x + 7y = 100 x,y are positive integers. How many pairs of x,y are possible? Solution: Given that x,y >= 1. So 7y < 100 y < 100/7 y <= 14 So 1 <= y <= 14. Now 3x = 100 - 7y If you put all the values of y one by one you see that RHS becomes divisible by 3 for y = 1,4,7,10,13. So answer is 5 such pairs are there. But why did we choose y for iterating and not x? Let's do it with x. 3x < 100 => x <= 33 So we would have to iterate 33 times and check for divisibility by 7 each time. So it is wiser to go for y. We can make the solution much simpler using modulo arithmetic . 3x = 100 - 7y Do modulo by 3 on both sides. 3x % 3 = (100 - 7y) %3 0 = 100 % 3 - 7y %3 %3 0 = 1 - (7 %3) (y%3) %3 0 = 1- 1.y % 3 y = 1 % 3 Since y goes from 1 to 14, there are 5 values which leave the remainder 1 when divided by 3.