# Fermats Little Theorem

• September 23rd 2010, 05:10 PM
ikurwae89
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 p|n^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^p-1 CONG 1 mod p

Using p=2k+1 --> p-1=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
• September 23rd 2010, 06:15 PM
Defunkt
Why would you set p=4? You are given that p is an odd prime. Specifically, p is odd so either $p \equiv 1 \ mod 4$ or $p \equiv 3 \ mod 4$

Assume by contradiction that $p \equiv \ 3 mod 4$ and proceed to use the previous results.
• September 23rd 2010, 06:34 PM
melese
To conclude the first two parts, you have $n^2\equiv-1\bmod p$ and $n^{p-1}\equiv1\bmod p$, where $p-1=2k$. Notice that $n^{p-1}=(n^2)^k\equiv(-1)^k\bmod p$. Now consider what happens if $k$ is odd.
• September 24th 2010, 11:22 PM
ikurwae89
How do you know that p cong 1 mod 4 or p cong 3 mod 4 ?
• September 25th 2010, 02:36 AM
Defunkt
p is odd. Can an odd number be congruent to 2 or 0 mod 4?
• September 25th 2010, 03:28 PM
ikurwae89
Nope? Because it's not divisible by 2 or 4 ?
• September 25th 2010, 04:18 PM
Defunkt
Prove it. It should take no more than 2 lines.