Solving Diophantine Equations: Find Largest Number of Chicken Nuggets

[InsaneMind]

So the other day I was asked a question about a problem by a friend. Having not been active in a math class in a VERY VERY long time I struggled with it at first... I believe it was worded as such...

Nick goes to McDonald's to buy chicken nuggets. Nick can only buy chicken nuggets in sets of 6, 9 and 20. After a bit, nick tries to figure out what's the largest number of chicken nuggets nick "cannot" buy. Help nick find out his answer, you can use any method you like (including guess and check)


Now originally I recognized that the problem is...

6a + 9b + 20c = n

Which I remembered as a diophantine equation, however I couldn't remember the formula to solve the problem. So I began using the guess and check method and arrived at the appropriate answer...checked his teachers guide to verify and then showed him how I did my guess and check method. His teacher gave out points to students whether they attempted the problem or not as long as they provided substantial work into it and/or arrived at an answer. (Basically as long as he tried he would get the extra-credit...I wish I had that teacher back in the day).


My question is...what's the proper formula for finding the answer?

Spoiler

The answer was 43

 

[Defennder]

I read about this problem some time back before. I don't think it has anything to do with Diophantine equation, it's more of modulo arithmetic. Except I can't recall the reasoning too.