
Fermats Little Theorem
Let n be a positive integer and suppose that p=2k+1 is an odd prime divisor of n^2+1.
CONG implies congruent to.
1)Show that n^2 CONG 1 mod p
I've done this by saying, because pn^2+1 > n^2+1 CONG mod p hence we arrive at the desired result by moving 1.
2) Using Fermat Little Theorem show that (n^2)^k CONG 1 mod p
I've done this by using the standard version of Fermat's little Theorem,
i.e a^p1 CONG 1 mod p
Using p=2k+1 > p1=2k and setting a=n
We get, n^(2k) CONG 1 mod p and fixing up n^2k to (n^2)^k CONG 1 mod p we arrive at the desired result.
3)Deduce from the preceding two parts, show that p CONG 1 mod 4.
Now here is where I'm in doubt, I'm confident with my previous answers(I don't have the solutions to these btw).
Setting p=4, causes problems with p=2k+1 > 3=2k .. k ?
So this is where I need your guidance.
Thanks

Why would you set p=4? You are given that p is an odd prime. Specifically, p is odd so either $\displaystyle p \equiv 1 \ mod 4$ or $\displaystyle p \equiv 3 \ mod 4$
Assume by contradiction that $\displaystyle p \equiv \ 3 mod 4$ and proceed to use the previous results.

To conclude the first two parts, you have $\displaystyle n^2\equiv1\bmod p$ and $\displaystyle n^{p1}\equiv1\bmod p$, where $\displaystyle p1=2k$. Notice that $\displaystyle n^{p1}=(n^2)^k\equiv(1)^k\bmod p$. Now consider what happens if $\displaystyle k $ is odd.

How do you know that p cong 1 mod 4 or p cong 3 mod 4 ?

p is odd. Can an odd number be congruent to 2 or 0 mod 4?

Nope? Because it's not divisible by 2 or 4 ?

Prove it. It should take no more than 2 lines.