Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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
show 3 more comments

4 Answers

up vote 1 down vote accepted

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.

share|improve this answer
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
show 15 more comments

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.

share|improve this answer
add comment

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.

share|improve this answer
+1 I missed that while reading it, you're right. –  fpqc Nov 19 '11 at 22:35
add comment


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.


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



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

share|improve this answer
This is a homework problem by the way. –  fpqc Nov 19 '11 at 22:56
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.