# Thread: Mod and primes?!

1. ## Mod and primes?!

Is it true that

1.if p is prime then n^(p squared)=n mod p for all natural numbers n??

2. n^7=n mod 35 for all natural numbers n

If so then what working should i show?and if not then what would be a counter-example??thanksss~~~

2. Originally Posted by bryan06
2. n^7=n mod 35 for all natural numbers n
n = 2 is a counterexample.

-Dan

3. Originally Posted by bryan06
1.if p is prime then n^(p squared)=n mod p for all natural numbers n??
This one is true by a version of Fermat's Little Theorem. We can state that
$p^2 \equiv 1~\text{(mod p - 1)}$

since p^2 - 1 is divisible by p - 1. So by Fermat's Little
$n^{p^2} \equiv n^1~\text{(mod p)}$

-Dan

4. thankss~~still a bit confused though i researched on wikipedia what fermat little theorem is but still cant figure out how you derived the following:
Originally Posted by topsquark
$p^2 \equiv 1~\text{(mod p - 1)}$
also how do you get from this line
Originally Posted by topsquark
since p^2 - 1 is divisible by p - 1.
to this line

Originally Posted by topsquark
So by Fermat's Little
$n^{p^2} \equiv n^1~\text{(mod p)}$
thankss

5. Originally Posted by topsquark
This one is true by a version of Fermat's Little Theorem. We can state that
$p^2 \equiv 1~\text{(mod p - 1)}$

since p^2 - 1 is divisible by p - 1. So by Fermat's Little
$n^{p^2} \equiv n^1~\text{(mod p)}$

-Dan
Or just note that $n^{p^2}=\left(n^p\right)^p\equiv n^p\equiv n\text{ mod }p$