# Number Theory: Problem 5

### Solution

Proof: We'll prove the contrapositive of the claim. That is, for all integers a and b, if $$\gcd(a,b) = 13$$ then $$3a-5b \not = 27$$.

So, let a and b be integers and suppose that $$\gcd(a,b) = 13$$. By the definition of gcd, 13 must divide a and 13 must divide b. By the definition of divides, this means that a=13m and b=13n, for some integers m and n.

Substituting these values into 3a-5b, we get $$3a-5b = 3(13m) -5(13n) = 13(3m-5n)$$

Suppose we let p=3m-5n. Then p is an integer, since m and n are integers. Furthermore, 3a-5b=13p. So 3a-5b is a multiple of 13. Since 27 is not a multiple of 13, 27 cannot be equal to 3a-5b. This is what we needed to show.

### Self-check

At the very start of the proof, did you say that you were switching to the contrapositive? Did you write out the contrapositive? In later math classes, you might have to be so explicit. We're making you do this now, because it's easy for beginners to get confused about the starting information and the desired conclusion for a contrapositive proof.

After you stated the contrapositive, did you declare your variables and your assumption that gcd(a,b)=13?

Did you declare the types of n and m (or whatever variable names you used) when they were introduced midway through the proof? The fact that they are integers is vital to making the rest of the proof work.

Did your proof end with the statement that 3a-5b cannot be equal to 27?

### Buggy proof 1

Proof: We'll prove the contrapositive of the claim. That is, for all integers a and b, if $$\gcd(a,b) = 13$$ then $$3a-5b \not = 27$$.

So, let a, b, n, m be integers and suppose that $$\gcd(a,b) = 13$$. By the definition of gcd, 13 must divide a and 13 must divide b. By the definition of divides, this means that a=13m and b=13n.

Substituting these values into 3a-5b, we get $$3a-5b = 3(13m) -5(13n) = 13(3m-5n)$$

Suppose we let p=3m-5n. Furthermore, 3a-5b=13p. So 3a-5b is a multiple of 13. But 27 is not a multiple of 13.

It's bad to declare n and m at the start of the proof. When you set up a variable without an explicit value, the assumption is that you're picking some arbitrary unconstrained value of that type. So m could be 3 or 127 or whatever. There's no reason why it should necessarily be a/13.

Towards the end, when we introduce the variable p, this proof fails to mention that p must be an integer (and briefly why). This is bad, because the definition of divides doesn't do anything useful unless the multiplier is forced to be an integer.

This proof stops one step short of the desired conclusion, so it leaves the reader hanging.

### Buggy proof 2

Proof: By contrapositive: $$\forall a,b \in \mathbb{Z}$$, if $$\gcd(a,b) = 13$$ then $$3a-5b \not = 27$$.

a and b are $$\mathbb{Z}$$'s. $$\gcd(a,b) = 13$$

13|a

13|b

a=13m and b=13n (m and n $$\mathbb{Z}$$'s)

$$3a-5b = 3(13m) -5(13n) = 13(3m-5n)$$

p=3m-5n

3a-5b=13p.

3a-5b is a multiple of 13. 27 is not a multiple of 13.

$$3a-5b \not = 27$$

Really? Would you want to read this if you were a TA for this class? Is this how you plan to present your brilliant new idea to your boss in a few years? Your English teacher is rolling over in her grave. Use connector words to help the reader understand the flow of your ideas.

Also $$\mathbb{Z}$$ is shorthand for the set of all integers. So there is no such thing as "a $$\mathbb{Z}$$".