The claim you need to prove is now the contrapositive of the original claim.
Did you write out your assumptions at the start of the proof, i.e. the information in the variable declarations and hypothesis of the claim (i.e. the hypothesis of the contrapositive)?
Did you write out the conclusion of the claim as the goal you need to reach at the end of the proof?
The definition given for gcd(p,q) is "the largest integer that divides both p and q." If gcd(p,q) = k, then you know three things:
Sometimes you need all three of these facts to prove a result involving gcd, but sometimes you just need some of them. In particular, you might not need the fact about k being the largest such integer.
Figure out intuitively why the conclusion must be true. Try picking some integers a and b whose gcd is 13. What is the value of 3a-5b? Why can't it be equal to 27?