Thread: Modular Arithmetic

Do you need to refer to 'Euler's Theorem' and 'Fermats Little Theorem' in the proof?

If p is a prime then you want a proof of Fermats Little Theorem. If p is composite then a proof of Euler's totient function will work.

Thank you.
p is prime.
I was looking at a proof of Fermats little Theorem on line but I still cannot see how ɸ(p) = p - 1.

Originally Posted by mlg

Thank you.
p is prime.
I was looking at a proof of Fermats little Theorem on line but I still cannot see how ɸ(p) = p - 1.

Well $\phi(n)$ is defined as the number of natural numbers such that $gcd(a,n)=1$ for $a>n$; another way of saying this is that a and n are relatively prime. If n is, say 9, then from the set $\{1,2,3,4,5,6,7,8\}$ only $\{1,2,4,5,7,8\}$ are a's which are relatively prime to 9, our n in this example, so $\phi(9)=6$.

In the specific case you bring up n is a prime (from $ɸ(p) = p - 1$). Since every natural number less then p is relatively prime to p all you have to do is count the natural numbers less then p to get your $\phi(p)$, which happens to be $p-1$.

The definition I have is; $\phi(n)=$the number of integers a that satisfy $0\leq a<n$ and $gcd(a,n)=1$

Thank you for your time and effort.
Although Modular arithmetic is new to me, what you have shown now makes a lot of sense to me.