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?