# Number Theory: Eulers Theorem

# Eulers Theorem

I’m going to try and explain Eulers Theorem, derived by the famous mathmatician Leonard Euler.

I’ll start by stating the theorem. As we hit new topics, I will sidetrack, tackle those topics and than continue on.

ɸmod𝒏𝒒

*Theorem.*

If

^{𝟇(𝒎)}≡ 1 (mod 𝒎)

We first must figure out how to 𝟇(𝒎). We will use a technique known as inclusion/exclusion. Namley, 𝟇(𝙥), where 𝙥 is a prime can be written

^{𝙠}) = 𝙥

^{𝙠}- 𝙥

^{𝙠-1}

*Example.* Find 𝟇(4).

We can break 𝟇(4) into its prime factors ⇒ 𝟇(2^{2}). Since 2 is a prime, we can use our rule of

^{𝙠}) = 𝙥

^{𝙠}- 𝙥

^{𝙠-1}

^{2}) = 2

^{2}- 2

^{2-1}

Which simplfies to,

^{2}) = 4 - 2

Which evaluates to,

^{2}) = 2