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

  • 0
    @Benjamin, yes.2011-11-19

4 Answers 4

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
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1818/discussion-between-benjamin-lim-and-matt)2011-11-20
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.

2

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