Maths Olympiad Prep

Library / /400 of 520

Number theory Difficulty 6.6 National olympiad Prove it

15. Let aa and bb be relatively prime positive integers and let nn be a positive integer. We call a solution x,yx, y of the linear diophantine equation ax+by=na x+b y=n nonnegative when both xx and yy are nonnegative.
a) Show that whenever n(a1)(b1)n \geqslant(a-1)(b-1) there is a nonnegative solution of this equation.
b) Show that if n=ababn=a b-a-b, then there are no nonnegative solutions.
c) Show that there are exactly (a1)(b1)/2(a-1)(b-1) / 2 positive integers nn such that the equation has a nonnegative solution.
d) The post office in a small Maine town is left with stamps of only two values. They discover that there are exactly 33 postage amounts that cannot be made up using these stamps, including 46c46 c. What are the values of the remaining stamps?

Solution

15. 7 cents and 12 cents

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.