Sobre equações diofantinas

Motivado pelo seguinte problema: http://ipsc.ksp.sk/contests/ipsc2010/real/problems/d.php

A minha modelagem pra esse problema chegou em uma quatro equações do tipo:
ax + by = c

No final das contas eu tinha que saber se essa equação tinha solução pra decidir quem ganhava a luta: o príncipe ou o dragão. E então? Como eu sei se uma equação dessa tem soluções inteiras?
Acontece que essa é uma equação diofantina linear, e ela só tem solução se c é o mdc(a, b) ou múltiplo do mdc(a, b). Bom resultado pra se lembrar.