## Proof by Exhaustion - Is this sufficient?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

### Proof by Exhaustion - Is this sufficient?

Assignment question!
"Prove the following theorem using cases:
‘No perfect square is of the form 4k + 3, where k is an integer.’"

So this is how I've gone about solving it (simplified):
Suppose n is some even/odd integer. That is, n =2m/2m+1, so n^2 is equal to... etc.
For both cases, assume for a contradiction that n^2 is of the form 4k+3 where k is an integer.
Then n^2=4k+3=2m^2 if n is even, and
n^2=4k+3=4m^2+4m+1 if n is odd.
By rearranging to get the value of k, I show that k is not an integer thus violating my original assumption, thus no perfect squares are of the form 4k+3.

So my question is this: Is it sufficient to say that since k is not an integer, then we have achieved our contradiction? Is this sufficient to prove the theorem if I've achieved this contradiction for even and odd numbers?
urza4315

Posts: 38
Joined: Thu Aug 25, 2011 9:49 am UTC

### Re: Proof by Exhaustion - Is this sufficient?

You don't need to do all of that for even integers, you just have to show that 4k+3 is odd.

dudiobugtron

Posts: 875
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: New Zealand

### Re: Proof by Exhaustion - Is this sufficient?

To put it differently: yes, what you did is more than sufficient.
Hey, like coding? Perhaps you should check out the red spider project.
Feel free to call me Julian. J+ is just an abbreviation.

Jplus

Posts: 1091
Joined: Wed Apr 21, 2010 12:29 pm UTC

### Re: Proof by Exhaustion - Is this sufficient?

Alternatively, notice that the operation of taking remainders when dividing by 4 "commutes" with multiplication, in the sense that if I take the remainder of xy, it is equal to the remainder of x times the remainder of y (possibly after you take remainders again, as 3*3=9, which should be 1).

Consequently, the fact that 0^2=0, 1^2=1, 2^2=4-> 0 (take remainders) and 3^2=9->1, means any square is of the form 4k or 4k+1.

(This is an example of something called modular arithmetic.)
DavCrav

Posts: 199
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

### Re: Proof by Exhaustion - Is this sufficient?

Now show that the sum of two perfect squares cannot be of the form 4k + 3.

PM 2Ring

Posts: 2588
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Return to Mathematics

### Who is online

Users browsing this forum: No registered users and 7 guests