# Prove the square root of 7 is irrational using the Division Algorithm and case reasoning

I proved this previously using proof by contradiction like so:

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!

-
bullet points are taking over proofs now? –  David Mitra Nov 19 '11 at 21:29
Whats wrong with bullet points? Its just personal preference no? –  Matt Nov 19 '11 at 21:34
@Matt I think by quotient-remainder they mean the division algorithm... –  fpqc Nov 19 '11 at 21:38
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.) –  Brian M. Scott Nov 19 '11 at 22:10
I wrote it, good point, will change –  Matt Nov 19 '11 at 22:14

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.

-
lol, 49 cases??? –  Matt Nov 19 '11 at 21:54
@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. –  fpqc Nov 19 '11 at 21:54
so it would read: 7a^2=b^2 -> 7(7l+m)^2=(7k+n)^2, factor those out? –  Matt Nov 19 '11 at 21:58
@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. –  fpqc Nov 19 '11 at 21:59
$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$ –  Matt Nov 19 '11 at 22:09

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 missed that while reading it, you're right. –  fpqc Nov 19 '11 at 22:35

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.

-

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

-
This is a homework problem by the way. –  fpqc Nov 19 '11 at 22:56