Sunday 17 December 2017

Extended Euclid: Solving Linear Diophantine Equation

Motivating Problem: Suppose, you are at the invisible cafeteria of CUET. In cafeteria, each cup of tea and coffee cost a and b taka respectively. You can buy any non-negative integer number cups of tea and coffee. If you have c taka, find out if it is possible to buy some cups of tea and coffee spending exactly c taka. We can model this problem like: ax+by=c.