# What is wrong with my proof by contradiction?

There exist no integers $a$ and $b$ for which $18a+6b=1$.

Proof: Assume that $18a+6b=1$. We find that $$6(3a + b)=1$$ which leads to $$3a+b=\frac16$$
We know that the sum of two integers can't produce a non-integer result, therefore a contradiction arises, as the proof demonstrates that two integers can produce a non-integer value. $\blacksquare$

My professor said that if one ends up with fractions in a proof, there is likely a problem. Can someone explain why this is the case?

• I really don’t know what he had in mind; I suspect that he was talking about some rather particular context, but it’s not clear what it might have been. Your argument here is fine. Oct 10, 2016 at 17:19
• Maybe your prof wanted a proof using integers, only. In that case you can stop at 6(3a + b)=1 and say that it proves $6|1$ which is false.
– dxiv
Oct 10, 2016 at 17:20
• @amWhy Thanks, but that's essentially the same as the answer already posted by KonKan. Plus, I'd have to explain why $6|1$ is false ;-)
– dxiv
Oct 10, 2016 at 17:36
• Perhaps your professor was implying that using fractions might implicitly require theorems that either rely on what you're proving (i.e. are circular) or are just generally beyond was is necessary for such a problem or what they desire to be used. (You could always ask the professor what they meant though) Oct 10, 2016 at 18:29
• My two cents. I'm assuming he doesn't like foo = 1/6 when we don't have the concept of the rationals yet. But if so he should have just said that. Oct 10, 2016 at 21:33

I'm assuming you're in a number theory class or abstract algebra. At this level of such a course, we haven't formally reintroduced $\Bbb Q$ so fractions don't formally exist yet.

We have multiplication and addition. And we have the integers.

The better proof is to show that $\gcd(18,6)=6$ and hence that the smallest positive linear combination of $18$ and $6$ we can make is $6$.

• Yes, I believe that is how my professor later explained it, using greatest common denominators. Oct 10, 2016 at 17:53
• Greatest common divisors* you mean Oct 10, 2016 at 18:05
• Sorry, but that's just wrong. There is no such thing as "the correct proof". His proof is fine, except for using $\frac{1}{6}$. You don't need to introduce $\Bbb Q$ to be able to say that $6$ does not divide $1$ in $\mathbb{Z}$. Oct 10, 2016 at 20:38
• Here I made it say "better" Oct 10, 2016 at 21:25
• The better proof is actually to say that he received a message from Jesus that there are no integers $a,b$ in a dream. This is called induction on Jesus. Oct 12, 2016 at 5:57

The core idea of your argument looks fine to me. I suspect what your professor had in mind, is that you should not write $3a + b = \frac{1}{6}$. You should simply say that $$6(3a + b)=1$$ is not possible in integers, since $6$ is not an invertible element in $\mathbb{Z}.$

$18a+6b=2\cdot(9a+3b)$ is an even number, so it cannot equal $1$ which is an odd number.

• This is a nice easy proof...but it doesn't answer the the OP's question of whether his was valid. Oct 11, 2016 at 12:41
• @Beska I had a comment about that under the main post, which I didn't repeat here.
– dxiv
Oct 11, 2016 at 15:47
• I can't see why it should make more sense to claim that 2 does not divide 1 than that 6 does not divide 1. Oct 12, 2016 at 5:24
• @miracle173 I didn't claim it did. But depending on the (untold) context, the notion that every integer is either even or odd (never both) may have been introduced earlier than the more general statement that 1 has no non-trivial divisors such as 6.
– dxiv
Oct 12, 2016 at 6:13
• This doesn't answer the question. Oct 12, 2016 at 9:56

Well, all the reasoning is sound here, but, actually, one might ask why exactly $\frac 1 6$ is not integer? To properly answer this, one needs to know how rational numbers are defined. Well, let us assume that $\frac 1 6$ is integer. That means that there is integer $k$ such that $\frac 1 6 = \frac k 1$. From the definition of rationals, this happens if and only if $6k = 1$ (as you can see, we are back to your original question). To finish argumentation, one argues that $6$ does not divide $1$ in $\Bbb Z$ to get contradition, so $\frac 1 6$ can't be integer.

• Isn't 6 does not divide 1 in Z literally equivalent to 1/6 is not in Z?
– dxiv
Oct 10, 2016 at 17:49
• Of course it is, but "$1/6$ is not integer" is statement about rational numbers, while "$6$ does not divide $1$ in $\Bbb Z$" is statement about integers. Since rationals are constructed from integers, I believe that "$6$ does not divide $1$" is more fundamental than the other one. @dxiv Oct 10, 2016 at 17:53
• @dxiv, I agree, this is just a speculation what the professor might find "morally wrong" with the proof using rationals. Oct 10, 2016 at 18:06
• 1/6 is not an integer because six of these buggers fit into the interval [0,1]. :)
– Kaz
Oct 10, 2016 at 18:24
• @Kaz, well yeah, but what does it even mean if you don't repeat the whole construction $\Bbb N\to \Bbb Z\to \Bbb Q$? Assuming you have $\Bbb Q$ by other means and not as field of fractions of $\Bbb Z$. Oct 10, 2016 at 18:29

Well here I think your professor means that if you add two integers, you should never get a number that is not an integer.

This is because the integers are "closed" under addition (and also multiplication). Mathematically speaking, any two elements of the integers say $a$ and $b$ can be combined as $a+b$ or $ab$ and still only give a result that is an integer.

Side note: why might the integers not be closed under division?

Try using the fact that sum , difference of even numbers produces even numbers only. $18a, 6b$ are even. I can't say exactly what he meant but I guess he meant using only properties explained till that moment.

You could just show the left-hand side is even for all integer $a$ and $b$, while RHS is always odd, so they are never equal.