I'm working on this homework problem:

Prove that if

and 30 are relatively prime, then

is a multiple of 60.

What I have so far is a case breakdown that seems to work, but I'm wondering if there are shortcuts I could take to reduce the number of cases or prove the result directly. Here's what I have so far:

implies that 2 does not divide a, therefore .

can be rewritten as the Diophantine equation . This, in turn, can be rewritten as . I have a theorem that guarantees, for any relatively prime to 60, exactly one solution for .

The case breakdown I mentioned, then, is taking all the numbers such that is less than 30 and relatively prime to 30 and demonstrating that 60 divides . Since , this results in eight cases.

Is there a better way to do this?