In a particular European city, there are only $7$ day tickets and $30$ day tickets to the public transport. The former costs $7.03$ euro and the latter costs $30$ euro. Aina the Algebraist decides to buy at once those tickets that she can travel by the public transport the whole three year (2014-2016, 1096 days) visiting in the city. What is the cheapest solution?
Suppose that Anan byus $m$ seven day tickets and $n$ $30$ day tickets. She must have enough tickets so we get the inequality $7m+30n\geq 1096$. The price of the tickets is $m\cdot 7.03+n\cdot 30=0.03m+7m+30n\geq 0.03m+1096.$ Let us find when $7m+30n=1096.$ The greatest common divisor of $7$ and $30$ is $1$. Apply the Euclidean algorithm to the equation $7m+30n=1$: $430=4\cdot 7+2$ and $7=3\cdot 2+1$ thus $1=7-3\cdot 2=7-3\cdot (30-4\cdot 7)=13\cdot 7-3\cdot 30.$ Therefore, $13\cdot 1096\cdot 7-3\cdot 1096\cdot 30=1096$ and $(13\cdot 1096-30t)\cdot 7-(3\cdot 1096-7t)\cdot 30=1096$ for all $t\in\mathbb{Z}$. The smallest $m$ can be found as $t$ is the largest integer satisfying $13\cdot 1096-30t\geq 0$ and $-(3\cdot 1096-7t)\geq 0.$ The largest $t$ satisfying $13\cdot 1096\geq 30t$ is $474$, and this gives $m=28$. We have $2\cdot 1096-7\cdot 474=-30<0.$ If one byus $28$ week tickets and $30$ $30$-days tickets, it will cost $1096+28\cdot 0.03=1096.84$. For any other combinations of $m$ and $n$ gives $0.03+7m+30n\geq 0.03m+1097\geq 1097.$ Thus the cheapest combination of tickets is $28$ week tickets and $30$ month tickets.