Thread: 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

Why would you set p=4? You are given that p is an odd prime. Specifically, p is odd so either or

Assume by contradiction that and proceed to use the previous results.

To conclude the first two parts, you have and , where . Notice that . Now consider what happens if 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.