# Stuck on a proof

• Feb 10th 2010, 03:26 PM
Selena
Stuck on a proof
I'm stuck on the final step in these two proofs:
1) For every natural number N that leaves remainder of 1 when divided by 5, there's a n^2 that also leaves remainder of 1 when divided by 5

n = 5k + 1 where k, an integer, is the quotient:
Then n^2 = (5k + 1)^2
n^2 = 25k^2 + 10k + 1
= 5(5k^2 + 2k) + 1

Stuck here...

let j be 5k^2 + 2k
if k is an integer, then 5k^2 + 2k is also an integer
n^2 = 5j + 1, where j is an integer quotient

And the very similar problem...

2) For every natural number N that leaves remainder of 4 when divided by 5, there's a n^2 that leaves remainder of 1 when divided by 5

n = 5j + 4 where j, an integer, is the quotiet:
Then n^2 = (5j + 4)^2
n^2 = 25j^2 + 40j + 16
= 25j^2 + 40j + 15 + 1
= 5(5j^2 + 8j + 3) + 1
= 5(j + 1)(5j + 3) + 1

Stuck here...

Thanks for any help.
• Feb 10th 2010, 10:05 PM
bmp05
hi selena,

you've proved it! There's nothing more to do... you might want to think about how you present the proof. The implication is:
$
(\forall n)(\exists j, k)(n = 5j + 1) \Rightarrow (n^2 = 5k + 1); n, j, k \in \mathbb{N}
$

and then you use your proof to show:
$
n^2 = 5(5j^2 + 2k) + 1
$

and notice that $k = 5j^2 + 2j \Rightarrow k \in \mathbb{N}$. You normally don't have to show that any two integers add or multiply to give another integer.