1
$\begingroup$

I proved this previously using proof by contradiction like so: enter image description here

I am not seeing where to start to prove it using the Quotient Remainder theorem or case reasoning however. Can anyone see the best way to go about doing this? Thanks!

enter image description here

  • 6
    bullet points are taking over proofs now?2011-11-19
  • 0
    Whats wrong with bullet points? Its just personal preference no?2011-11-19
  • 0
    @Matt I think by quotient-remainder they mean the division algorithm...2011-11-19
  • 3
    What’s wrong with bullet points is that they encourage poor writing. Whoever wrote that extract apparently doesn’t know what a sentence is, or what *in lowest terms* means. (A fraction can be in lowest terms; a pair of integers can’t.)2011-11-19
  • 0
    I wrote it, good point, will change2011-11-19
  • 0
    @Matt Did you type that out in Microsoft Word?2011-11-19
  • 0
    The worst thing in this proof is "bullet point #3". So I have to start at the top and count down 1, 2, 3?! Why use bullets when you could use numbers? This is mathematics, after all.2011-11-19
  • 0
    @Benjamin, yes.2011-11-19

4 Answers 4

1

$$\sqrt{7}=\frac{m}{n}\,.$$

with $m,n$ relatively prime.

By Quotient-Reminder Theorem $m= qn+r$ for some $0 \leq r < n$. Then $n,r$ are also relatively prime.

Then

$$\sqrt{7}=q+\frac{r}{n} \,,$$

with $0 \leq \frac{r}{n} \leq 1$. It is easy to argue now that since $4 < 7 <9$, $q=2$.

Then

$$7=4+4\frac{r}{n}+\frac{r^2}{n^2}$$

Thus $r^2+4rn=3n^2$.

Now a case by case analysis $\mod 4$, shows that this equation can only have solution only when $r,n$ are even, contradiction. The analysis is easy $x^2=0,1 \mod 4$.

P.S. I highly doubt that this is the wanted solution...

  • 1
    This is a homework problem by the way.2011-11-19
3

If the use of division algorithm is not compulsory, then a simple argument using prime factorization theorem will suffice to prove that $7|a^2 \implies 7|a$.

Consider the contra-positive statement $7\nmid a \implies 7\nmid a^2$. The fact that $7$ does not divide $a$ means that $a$ does not have $7$ as its prime factor. Thus $a^2$ will not have any $7$ as prime factor too. Hence $a^2$ is not divisible by $7$ either.

2

The proof is incomplete since it omits proof of the crucial inference $\rm\ 7\ |\ a^2\ \Rightarrow\ 7\ |\ a\:.\ $ For a fixed prime such as $7$ this can indeed by proved by brute-force case analysis. It's equivalent to showing that, mod $7,$ $\rm\ n\not\equiv 0\ \Rightarrow\ n^2 \: \not\equiv 0\:,\:$ which is true since $\rm\: \{\pm1,\:\pm2,\:\pm3\}^2 \equiv \{1,4,2\} \not\ni 0.$

Thus you need only translate the above three squarings from the language of modular arithmetic into the language of remainders to obtain your sought proof. For example, the first case is $\rm\ (\pm1 + 7\ k)^2 = 1 + 7\:k\ (\pm2 + 7\:k)\:$ is not divisible by $7$ since it has remainder $1\:.\:$ Finally, of course, every integer has the form $\rm\ n = r + 7\ k\ $ for $\rm\ r \in \pm \{0,1,2,3\}\ $ (this is the balanced residue system - the use of which reduces our work by half).

NOTE $\ $ Said inference is a special case of the prime divisor property $\rm\ p\ |\ a\:b\ \Rightarrow\ p\ |\ a\ \ or\ \ p\ |\ b\:.\ $ This is the key property that guarantees uniqueness of prime factorizations. In more general domains atoms (irreducibles) need not be prime, i.e. need not satisy the prime divisor property, so there may be nonunique factorizations. When, as above, one is implicitly invoking powerful properties such as unique factorization (or equivalent properties such as the prime divisor property) it is important to explicitly mention such. Otherwise the proof can (rightfully) be accused of being incomplete, circular, etc - gaffes that held true for centuries before Gauss brought to the fore the key foundational role played by these results throughout number theory.

1

I think you can do it like this, though it may or may not help you (It seemed the most obvious way to me since you mentioned the division algorithm).

By the division algorithm, any integer in the universe can be written in the form $7k + n$, where $0 \leq k \leq 6$.

  1. Write $a = 7l +m $, $b = 7k + n$, where $l,m,k,n$ are integers and $ 0 \leq n,m \leq 6$.

  2. At the step above in your text where they equate $7a^2 = b^2$, put these in for $a$ and $b$.

You should now get an expression that says

A multiple of seven $=$ (Some expression in terms of $m$ and $n$ ).

Since we have bounds on what $m,n$ can be, you can now bash out the 49 cases to show that this is not possible.

  • 0
    lol, 49 cases???2011-11-19
  • 0
    @Matt well yes because you have seven choices for $m$, seven choices for $n$. But you should be able to do it under 30 minutes.2011-11-19
  • 0
    so it would read: 7a^2=b^2 -> 7(7l+m)^2=(7k+n)^2, factor those out?2011-11-19
  • 0
    @Matt Do write your comments in latex. Tell me when you expand stuff what happens, and then equate the quantities like I told you to do.2011-11-19
  • 0
    $7a^2=b^2$ --> $7(7l+m)^2=(7k+n)^2$ --> $7(49l^2+14lm+m^2)=49k^2+14kn+n^2$ --> $343l^2+98lm+7m^2=49k^2+14kn+n^2$2011-11-19
  • 0
    Hmm, I don't see where to go from here to prove anything?2011-11-19
  • 0
    Slowly, how about $7(49k^2 + 14nk - 7l^2 - 2ml) = m^2 - 7n^2$? Now tell me how does this help you?2011-11-19
  • 0
    hmm, how are you getting that re-arrangment? just algebra?2011-11-19
  • 0
    Yes. By the way you wrote in your question that $7b^2 = a^2$. Now you are writing $7a^2 = b^2$. Please be consistent in the variables that you use. It does not matter anyway, but if we work from what you wrote above we have $7(49l^2 + 14lm - 7k^2 - 2kn) = n^2 - 7m^2$. Now do you know how to go?2011-11-19
  • 0
    Ok, now I see how you go this, now we are to evaluate for each variable from 0-7 and if the equality is false, so is the assumption that sqrt(7) is rational?2011-11-19
  • 0
    @Matt I think you mean from $0 - 6$. There is that tricky case when $m = n = 0$, but then I think it is redundant because it takes you back to square one.2011-11-19
  • 0
    @Matt How is the problem going?2011-11-19
  • 0
    just getting back from a break! will let you know any moment2011-11-20
  • 0
    ok so I evaluated for the first 4 cases, all are false besides first case: 0. Case 4,5,6 are obviously going to be false also. Is this what I was supposed to be doing or am I completely missing something your trying to get across: http://imgur.com/ZYry12011-11-20
  • 0
    @Matt I don't think you are doing this right. You should just concentrate mainly on the right hand side. Example. The case $m = 1$, $n = 0,1,2,3,4,5,6$. The right hand side will then be: $1,-6, -27, -62, -111, -174,-251$ which are all not multiples of 7, so this case is eliminated.2011-11-20
  • 0
    Am I not supposed to evaluate l or k?2011-11-20
  • 0
    $l$ and $k$ are any integers. The thing is, we only 49 possibilities for $m$ and $n$. If we can show that each one of these 49 possibilities results in something impossible, then you're done. The idea is that we want to be concentrating on the *remainder*, which is $m$ and $n$. Tell me then why do you want to use the division algorithm?2011-11-20
  • 0
    this seems really far out from what i've been learning in class. Is this a standard way of case reasoning?2011-11-20
  • 0
    @Matt Would you like to move this to chat?2011-11-20
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1818/discussion-between-benjamin-lim-and-matt)2011-11-20