Waste less time on Facebook — follow Brilliant.
Number Theory

Linear Diophantine Equations

Postage Stamp Problem / Chicken McNugget Theorem


A family restaurant sells nuggets in packages of two sizes, 7 nuggets and 12 nuggets. Is there a maximum number of nuggets that \( \color{red}{\text{cannot}} \) be expressed as a nonnegative combination of these package sizes?

Yes or No?

Are there any non-negative integer solutions to the equation

\[ 13m + 15n = 170? \]

Yes or No?

If \( a>4 \) is an integer that is \( \color{red}{\text{not}} \) a multiple of 13, can we express \( 11a-39 \) as a non-negative integer linear combination of \( a \) and 13?

In a fast food restaurant, you can order buckets of doughnuts only in quantities of 7 and 19 a bucket. What is the \( \color{red}{\text{second}} \) largest number of doughnuts you \( \color{red}{\text{cannot}} \) buy?

There are only two kinds of postage stamps: 12 cents and 25 cents. For some values, you can get them as linear combinations of two kinds. For others, you cannot. What is the largest possible value you \( \color{red}{\text{cannot}} \) attain no matter which combination you choose? Give your answer in cents.


Problem Loading...

Note Loading...

Set Loading...