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!


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.
