Math in division in two cases proof

Using division in two cases, I have to solve the problem

The fourth power of any integer has the form 4k or 4k+1 For some integer k.

 Claim: For all integers z, z^4 equals 4k or 4k+1 For some integer k.

Proof: Let integer z be given.
By the Division Algorithm, There exists an integer k such that z^4=4k or z^4=4k+1.

Case1: Suppose there exists an integer k such that z^4=4k.
Then ....

Case2: Suppose there exists an integer k such that z^4=4k+1
Then...


I am struggling with the math to actually prove these things. I can set it all up I just can't finish it.

• "By the Division Algorithm, There exists an integer $k$ such that $z^4=4k$ or $z^4=4k+1$." This is not true. A priori, it is also possible that $z^4 = 4k + 2$ or $z^4 = 4k + 3$. – wgrenard Nov 17 '17 at 16:55
• "By the Division Algorithm, There exists an integer k such that z^4=4k or z^4=4k+1." No. That is what you are trying to prove. "Case1: Suppose there exists an integer k such that z^4=4k. Then ...." Then $z^4 = 4k$ and you are done. "Case2: Suppose there exists an integer k such that z^4=4k+1 Then..." then $z^4 = 4k + 1$ and you are done. You assumed what you wanted to prove and therefore you didn't have to do anything at all. – fleablood Nov 17 '17 at 16:57
• Someone is going to have to explain to me why so many students start proofs as "Prove THISTHINGWEDONTKNOWYET. Proof: Since we know THISTHINGWEDONTKNOWYET..." I honestly can not understand it. – fleablood Nov 17 '17 at 17:18

Case 1: Suppose $n$ is even. Then $n=2m$. Then $n^4=16 m^4=4(4m^4)=4k$.

Case 2: Suppose $n$ is odd. Then $n=2m+1$. Then \begin{align}n^4&=(2m+1)^4\\&=16m^4+4(8m^3)+6(4m^2)+4(4m)+1\\&=4(4m^4+8m^3+6m^2+4m)+1\\&=4k+1\end{align}

Claim: For all integers z, z^4 equals 4k or 4k+1 For some integer k.

Proof: Let integer z be given. By the Division Algorithm, There exists an integer k such that z^4=4k or z^4=4k+1.

No. By the division algorithm there exists an integer $k$ such that $z^4 = 4k$ or $z^4 = 4k + 1$ or $z^4 = 4k + 2$ or $z^4 = 4k + 3$.

That $z^4 = 4k$ or $z^4 = 4k + 1$ are the only two that can occur and $z^4 = 4k + 2$ or $z^4 = 4k + 3$ can not occur is precisely what you want to prove.

Case1: Suppose there exists an integer k such that z^4=4k.
Then ....


Then you don't have to go any further. This was one of the cases you had to prove. You assumed it was true so there is nothing more to do.

This is why you don't assume what you want to prove. Because if you assume what you want to prove you don't actually do anything.

Case2: Suppose there exists an integer k such that z^4=4k+1
Then...


ditto.

What you have to do is:

Claim: For all integers z, z^4 equals 4k or 4k+1 For some integer k.

Proof: Let integer z be given. By the Division Algorithm, There exists an integer k such that z^4=4k or z^4=4k+1 or $z^4 = 4k +2$ or $z^4 = 4k +3$.

Case1: Suppose there exists an integer k such that z^4=4k.
Then .... we are done.

Case2: Suppose there exists an integer k such that z^4=4k+1
Then... we are done.

Case3: Suppose there exists an integer k such that $z^4=4k+2$
Then... we have a contradiction somehow.

Case4: Suppose there exists an integer k such that $z^4=4k+3$
Then... we have a contradiction somehow.


But that is actually not the best way (though) it can be done.

It'd better not to use the division algorithm on the result $z^4$ but on the input $z$.

Proof: Let integer z be given. By the Division Algorithm, There exists an integer k such that z=4k or z=4k+1 or $z = 4k +2$ or $z = 4k +3$.

Case1: Suppose there exists an integer k such that z=4k.
Then .... $z^4 = 4^4k^4 = 4(4^3k^4)=4M; M = 4^3k^4$ and we are done.

Case2: Suppose there exists an integer k such that z=4k+1
Then... $z^4 = 4^4k^4 + 4*4^3*k^3 + 6*4^2*k^2 + 4*4k + 1 = 4M + 1; M = 4^3k^4 + ... whatever$.

Case3: Suppose there exists an integer k such that $z=4k+2$
Then... $z^4 = 4^4k^4 + 4*2*4^3*k^3 + ...$ .... hey! this is a really waste of effort and time!  Why are we doing $4$ and $4^4$ when $2^4 =16$ is also a multiple of $4$ and $2$ is much simpler to deal with?

Case4: Suppose there exists an integer k such that $z=4k+3$
Then... screww this


Instead we can do:

Proof: Let integer z be given. By the Division Algorithm, There exists an integer k such that z=2k or z=2k+1.

Case1: Suppose there exists an integer k such that z=2k.
Then .... $z^4 = 2^4k^4 =16k^4 =4M; M = 4k^4$ and we are done.

Case2: Suppose there exists an integer k such that z=2k+1
Then... $z^4 = 2^4k^4 + 4*2^3k^3 + 6*2^2k^2 + 4*2k + 1 = 4M + 1; M = 4k^4 + 8k^3 + 6k^2 + 2k$ and we are done..


The second line in your proof assumes the very thing you want to prove. The Division Algorithm provides four cases, and you want to narrow it down to two:

Proof. Let $z$ be given. By the division algorithm, there exist integers $k$ and $q$ with $0 \leq q < 4$ such that $z = 4k + q$.

Now expand $z^4$ and see what remainders are possible modulo 4.

• with $0\le q\le 3$ – John Doe Nov 17 '17 at 18:27
• @JohnDoe: Right you are. I don't know how I left that part out. – Matthew Leingang Nov 17 '17 at 18:54