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
then,
𝒂𝟇(𝒎) ≡ 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
This tells us how to find 𝟇 of a prime. We can show an example of this.

Example. Find 𝟇(4).

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

𝟇(𝙥𝙠) = 𝙥𝙠 - 𝙥𝙠-1
So,

𝟇(22) = 22 - 22-1

Which simplfies to,

𝟇(22) = 4 - 2

Which evaluates to,

𝟇(22) = 2