21
$\begingroup$

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?

Improve this question
$\endgroup$
  • 7
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Oct 10 '16 at 17:19
  • 26
    $\begingroup$ 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. $\endgroup$ – dxiv Oct 10 '16 at 17:20
  • 2
    $\begingroup$ @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 ;-) $\endgroup$ – dxiv Oct 10 '16 at 17:36
  • 8
    $\begingroup$ 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) $\endgroup$ – Milo Brandt Oct 10 '16 at 18:29
  • 2
    $\begingroup$ 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. $\endgroup$ – fleablood Oct 10 '16 at 21:33
27
$\begingroup$

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$.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Yes, I believe that is how my professor later explained it, using greatest common denominators. $\endgroup$ – Benjamin Thomas Oct 10 '16 at 17:53
  • 2
    $\begingroup$ Greatest common divisors* you mean $\endgroup$ – Phillip Hamilton Oct 10 '16 at 18:05
  • 14
    $\begingroup$ 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}$. $\endgroup$ – Vincent Oct 10 '16 at 20:38
  • 2
    $\begingroup$ Here I made it say "better" $\endgroup$ – Phillip Hamilton Oct 10 '16 at 21:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Billy Rubina Oct 12 '16 at 5:57
23
$\begingroup$

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}.$

Improve this answer
$\endgroup$
23
$\begingroup$

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

Improve this answer
$\endgroup$
  • 11
    $\begingroup$ This is a nice easy proof...but it doesn't answer the the OP's question of whether his was valid. $\endgroup$ – Beska Oct 11 '16 at 12:41
  • $\begingroup$ @Beska I had a comment about that under the main post, which I didn't repeat here. $\endgroup$ – dxiv Oct 11 '16 at 15:47
  • $\begingroup$ 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. $\endgroup$ – miracle173 Oct 12 '16 at 5:24
  • $\begingroup$ @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. $\endgroup$ – dxiv Oct 12 '16 at 6:13
  • 2
    $\begingroup$ This doesn't answer the question. $\endgroup$ – reinierpost Oct 12 '16 at 9:56
12
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Isn't 6 does not divide 1 in Z literally equivalent to 1/6 is not in Z? $\endgroup$ – dxiv Oct 10 '16 at 17:49
  • 11
    $\begingroup$ 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 $\endgroup$ – Ennar Oct 10 '16 at 17:53
  • 3
    $\begingroup$ @dxiv, I agree, this is just a speculation what the professor might find "morally wrong" with the proof using rationals. $\endgroup$ – Ennar Oct 10 '16 at 18:06
  • 1
    $\begingroup$ 1/6 is not an integer because six of these buggers fit into the interval [0,1]. :) $\endgroup$ – Kaz Oct 10 '16 at 18:24
  • 2
    $\begingroup$ @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$. $\endgroup$ – Ennar Oct 10 '16 at 18:29
2
$\begingroup$

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?

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

Your proof is correct.
However, it's a bit too complicated.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.