2

Right now I'm studying how to find errors in proofs by looking for common mistakes such as circular reasoning, using examples etc. I haven't had too many problems for the most part but I've run into a proof for which I can find no errors. It goes as follows:

Claim: Let $u, m, n$ be three integers. If $u \mid mn$ and $\gcd(u, m) = 1$, then $m = \pm 1$.

"Proof": If $\gcd(u, m) = 1$, then $1 = us + mt$ for some integers $s, t$. If $u \mid mn$, then $us = mn$ for some integer $s$. Hence, $1 = mn + mt = m(n + t)$, which implies that $m \mid 1$, and therefore $m = \pm 1$.

I'm looking for simple mistakes but for the most part I can't see anything wrong with this particular proof. Any tips on finding what I'm missing are greatly appreciated.

Community
  • 1
Johnathan Scott
  • 333
  • 1
    Seems like $s$ should be used only once at the point $1=us+mt$ yet it gets used multiple times in other spots? – graydad Jan 05 '15 at 03:49
  • 1
    The first line already has a mistake: $$3\mid 4\cdot3;,;;\text{yet};;4\neq\pm1 $$ – Timbuc Jan 05 '15 at 03:50
  • 1
    @Timbuc The first line is the statement that we are trying to prove (which is of course false), and the rest is the (erroneous) proof. – Ted Jan 05 '15 at 03:52
  • @Ted Thanks. It'd be probably wise to state that specifically. – Timbuc Jan 05 '15 at 03:53

2 Answers2

3

If $\gcd(u,m)=1,$ then $1=us_1+mt$ for some integers $s_1,t.$ If $u\mid mn,$ then $us_2=mn$ for some integer $s_2.$ There is no guarantee that $s_1=s_2.$ The error is one of equivocation.

As it turns out, we can make $s_1=s_2$ if and only if $m=\pm 1,$ precisely because in such a case, we would be able to conclude that $m\mid 1.$

For an example meeting the hypotheses, but not the conclusion, consider $u=2,$ $m=3,$ and $n=4.$ Clearly, $s_2$ in that case is $6,$ but we cannot write $1=us_2+mt=12+3t$ with $t$ an integer, as $m=3$ will always divide $12+3t$ if $t$ is an integer. However, there are still $s_1$ that suffice. For example, we can let $s_1=1$ and $t=-1,$ or we can let $s_1=3$ and $t=-4.$ More generally, in this case, we will have $1=us_1+mt$ for some integers $s_1,t$ if and only if $s_1=1+2k=1+mk$ and $t=-1-3k=-1-uk$ for some integer $k.$

Cameron Buie
  • 102,994
1

If a simple counterexample is available, one technique you can use is just to check each statement in the proof to see if it holds for your counterexample. The first false statement is the place where the error was introduced.

In this case, we have the easy counterexample of $u=1, m=2, n=1$.

If $\gcd(u,m)=1$, then $1=us+mt$ for some integers $s,t$.

This is true; we can take $s=1, t=0$.

If $u\mid mn$, then $us=mn$ for some integer $s$.

Now at this point you will probably notice that $s$ has been used before because the very last thing you did was to pick a value for $s$. But suppose you somehow didn't notice. Then you go ahead and say "okay, we ought to have $us = mn$". But that's $1 = 2$. WAIT, SOMETHING IS WRONG. (klaxon bells ring).

And then you stop right there and ignore the rest of the proof until you figure out how you were tricked into accepting $1=2$.

MJD
  • 65,394
  • 39
  • 298
  • 580