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?

$\endgroup$
6
  • 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 21:33

7 Answers 7

Reset to default
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$.

$\endgroup$
5
  • 1
    $\begingroup$ Yes, I believe that is how my professor later explained it, using greatest common denominators. $\endgroup$
    – Benjamin Thomas
    Oct 10, 2016 at 17:53
  • 2
    $\begingroup$ Greatest common divisors* you mean $\endgroup$
    – Phillip Hamilton
    Oct 10, 2016 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, 2016 at 20:38
  • 2
    $\begingroup$ Here I made it say "better" $\endgroup$
    – Phillip Hamilton
    Oct 10, 2016 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$
    – Red Banana
    Oct 12, 2016 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}.$

$\endgroup$
23
$\begingroup$

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

$\endgroup$
6
  • 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, 2016 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, 2016 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, 2016 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, 2016 at 6:13
  • 2
    $\begingroup$ This doesn't answer the question. $\endgroup$
    – reinierpost
    Oct 12, 2016 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.

$\endgroup$
7
  • 1
    $\begingroup$ Isn't 6 does not divide 1 in Z literally equivalent to 1/6 is not in Z? $\endgroup$
    – dxiv
    Oct 10, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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?

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

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

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