Here's an excerpt from one of my old sci.math posts which explains a geometric viewpoint.
Notice that we may normalize any representation $\rm\ N\ =\ P\ X + Q\ Y\ $ so that $\rm\ 0 \le X < Q\ $ by adding a certain integral multiple of $\rm\ (-Q,P)\ $ to $\rm\:(X,Y)\:.\ $ From this observation follows this
LEMMA $\rm\ \ N = P\ X + Q\ Y\ $ for some integers $\rm\ X,Y \ge 0\ $
iff its normalization has $\rm\: Y \ge 0\:$.
Proof $\rm\ \ \ X,Y \ge 0\ $ implies that normalization requires addition of $\rm\:(-Q,P)\:$ zero or more times,$\ $ and this preserves the condition $\rm\: Y \ge 0\:.\ $ Conversely if the normalization has $\rm\: Y < 0\:,\ $ then $\rm\:N\:$ has no
representation with $\rm\ X, Y \ge 0\:,\ $ because to shift $\rm\: Y > 0\: $
requires adding $\rm\ (-Q,P)\ $ at least once, which shifts $\rm\: X < 0\:.\ $
Finally, since $\rm\ X\ P + Y\ Q\ $ is increasing in both $\rm\: X,Y\:,\ $
it is clear that the largest non-representable number $\rm\: N\:$ has normalization
$\rm\: (X,Y)\ =\ (Q-1,-1)\:,\: $ therefore $\rm\ N\ =\ PQ - P - Q\:.\quad\quad $ QED
Notice that the proof has a vivid geometric picture:
representations of $\rm\:N\:$ correspond to lattice points $\rm\:(X,Y)\:$
on the line $\rm\ N = P\ X + Q\ Y\ $ with negative slope $\rm = -P/Q\:.\ $
Normalization is achieved by shifting forward/backward
along the line by integral multiples of vector $\rm\:(-Q,P)\:$
until you land in the normal strip where $\rm\ 0 \le X < Q-1\:.\ $
From this viewpoint, the proof becomes crystal clear.
In case you're interested, the class I'm teaching
is linear algebra, but as you can see I like to
give puzzles to the class which are not necessarily
related to the material (in an obvious way).
Here the underlying linear structure is a $\mathbb Z$-module,
a generalization of a vector space; i.e. here the
scalars are the integers so have only the structure
of a ring, not a field. Unless you've already taught
some module theory, it might be tricky to precisely
explain the relationship to vector spaces.
Finally it should be mentioned that there has been much
written on this classical problem. To locate such work
you should ensure that you search on the many aliases,
e.g. postage stamp problem, Sylvester/Frobenius problem,
Diophantine problem of Frobenius, Frobenius conductor,
money changing, coin changing, change making problems,
h-basis and asymptotic bases in additive number theory,
integer programming algorithms and Gomory cuts,
knapsack problems and greedy algorithms, etc.