Proof within elementary number theory Prove this: Let n and m be positive integers. if m is even, and n is not divisible by 4, then m^2 + n is also not divisible by 4.
Im unsure how to start, and have been wrestling with proving by contradiction by saying n IS divisible by 4 and by saying so that m^2 + n IS divisible by 4 but i dont think that works at all.. any help would be great!
 A: You were on the right way.
If $m$ is even, then you can write $m=2k$. Then $m^2=4k^2$ is divisible by 4.
Now suppose by contradiction that $m^2+n $ is divisible by 4, i.e
$m^2+n =4 \ell $. Then
$$
n=4\ell-m^2=4(\ell-k^2),
$$
that is $n$ would be divisible by 4, a contradiction.
A: A couple of hints.  If $m$ is even then can you prove that $m^2$ is divisible by $4$?
And do you know that if $A$ is divisible by $k$ then $A+B$ is divisible by $k$ if and only if $B$ is divisible by $k$?
Can you put these all together?
Maybe you can use the division Theorem:  For any integer $M$ and any natural number $n$ there are unique integers $q,r$ where $M = n\cdot q + r$ and $0\le r < n$.  (Think of it as $r$ is the remainder when you divide $M$ by $n$ and $q$ is the quotient rounded down to the nearest interval).
Try it on your own and then read below how I put it together 
=========
$m$ is even so there is an integer $k$ so that $m = 2k$.
That means $m^2 = 4k^2$ so $4|m^2$.
[Lemma:  If $k|A$ then $k|A+B$ if and only if $k|B$.  Pf: Let $A=kn$, if $4|A+B$ then there is an $m$ so that $A+B = 4m$. That means $B = 4m-A=4m-4n=4(m-n)$ and $4|B$.  Otherwise if $4|B$ then there is an $k$ so that $B = 4k$ and $A+B = 4m + 4k = 4(m+k)$ and $4|A+B$.]
So $4|m^2 + n$ if and only if $4|4k^2 +n$ if and only if $4|n$.  But we were told $4\not \mid n$.
... of course... that's just how I worded it.  You can prove it any way you want.
