# Number Theory: Problem 5

### Hints

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:

- k divides p
- k divides q
- k is the largest integer with these two properties

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?