Euler’s Theorem

students, imagine you need to find a huge power like $7^{100}$, but only care about the remainder when dividing by $20$. That kind of problem looks massive at first, yet number theory gives us a shortcut 🧠✨. Euler’s theorem is one of the most useful tools for working with remainders, and it connects directly to Fermat’s Little Theorem, modular arithmetic, and the function $\phi(n)$.

Introduction: why Euler’s theorem matters

The main idea behind Euler’s theorem is that some powers repeat in a predictable pattern when we work modulo $n$. Instead of calculating enormous numbers directly, we can often reduce the exponent and still get the same remainder.

In this lesson, you will learn how Euler’s theorem works, what the function $\phi(n)$ means, when the theorem can be used, and how it fits into the bigger picture of Fermat and Euler. By the end, students, you should be able to explain the theorem clearly and use it to solve remainder problems ✅.

The key idea: coprime numbers and repeating remainders

Euler’s theorem applies when two numbers are coprime, which means they have no common factor greater than $1$. In symbols, this is written as $\gcd(a,n)=1$.

The theorem says:

$$a^{\phi(n)} \equiv 1 \pmod n \quad \text{when } \gcd(a,n)=1$$

Here, $\phi(n)$ is Euler’s phi function, which counts how many integers from $1$ to $n$ are coprime to $n$.

Let’s unpack that carefully:

• $a$ is the number being raised to a power.
• $n$ is the modulus, the number we are dividing by to find remainders.
• $\phi(n)$ counts the positive integers less than or equal to $n$ that do not share any factors with $n$ except $1$.
• The result $a^{\phi(n)} \equiv 1 \pmod n$ means the remainder is $1$ after dividing by $n$.

This is powerful because it gives a cycle length for powers of $a$ modulo $n$ 📘.

Understanding Euler’s phi function $\phi(n)$

To use Euler’s theorem well, students, you need to understand $\phi(n)$.

If $n$ is prime, then every number from $1$ to $n-1$ is coprime to $n$, so:

$$\phi(n)=n-1 \quad \text{when } n \text{ is prime}$$

For example:

• $\phi(7)=6$ because $1,2,3,4,5,6$ are all coprime to $7.
• $\phi(8)=4$ because only $1,3,5,7$ are coprime to $8.

You can also use the formula for prime powers and products of distinct primes, but for many syllabus problems, counting directly is enough.

Example: find $\phi(10)$.

Numbers from $1$ to $10$ are $1,2,3,4,5,6,7,8,9,10.

The ones coprime to $10$ are $1,3,7,9.

So:

$$\phi(10)=4$$

Now Euler’s theorem tells us that for any $a$ with $\gcd(a,10)=1$,

$$a^4 \equiv 1 \pmod {10}$$

That is a huge shortcut.

Statement of Euler’s theorem

The formal statement is:

If $\gcd(a,n)=1$, then

$$a^{\phi(n)} \equiv 1 \pmod n$$

This theorem is part of the broader study of Fermat and Euler because it generalizes Fermat’s Little Theorem. Fermat’s theorem works when the modulus is prime; Euler’s theorem works for many composite moduli too, as long as $a$ and $n$ are coprime.

That makes Euler’s theorem more general and often more flexible 🔑.

Example 1: finding a remainder with a large exponent

Let’s use Euler’s theorem to find the remainder of $7^{100}$ when divided by $20$.

First check whether $7$ and $20$ are coprime:

$$\gcd(7,20)=1$$

So Euler’s theorem applies.

Next find $\phi(20)$.

The numbers from $1$ to $20$ that are coprime to $20$ are:

$$1,3,7,9,11,13,17,19$$

There are $8$ of them, so:

$$\phi(20)=8$$

Then Euler’s theorem gives:

$$7^8 \equiv 1 \pmod {20}$$

Now rewrite the exponent $100$ as a multiple of $8$ plus a remainder:

$$100=12\cdot 8+4$$

So:

$$7^{100}=\left(7^8\right)^{12}\cdot 7^4$$

Taking modulo $20$:

$$7^{100}\equiv 1^{12}\cdot 7^4 \equiv 7^4 \pmod {20}$$

Now calculate $7^4$ modulo $20$:

$$7^2=49\equiv 9 \pmod {20}$$

$$7^4=(7^2)^2\equiv 9^2=81\equiv 1 \pmod {20}$$

Therefore:

$$7^{100}\equiv 1 \pmod {20}$$

So the remainder is $1$.

Example 2: using the theorem with a prime modulus

Suppose we want the remainder of $3^{202}$ when divided by $11$.

Because $11$ is prime:

$$\phi(11)=10$$

Euler’s theorem says:

$$3^{10}\equiv 1 \pmod {11}$$

Now reduce the exponent:

$$202=20\cdot 10+2$$

So:

$$3^{202}=\left(3^{10}\right)^{20}\cdot 3^2$$

Modulo $11$:

$$3^{202}\equiv 1^{20}\cdot 3^2\equiv 9 \pmod {11}$$

So the remainder is $9$.

This example shows the close connection between Euler’s theorem and Fermat’s Little Theorem. When $n$ is prime, Euler’s theorem becomes exactly the same idea as Fermat’s theorem, since $\phi(n)=n-1$.

How Euler’s theorem fits into Fermat and Euler

Euler’s theorem sits at the center of the Fermat and Euler topic. Here is the relationship:

• Fermat’s Little Theorem works when the modulus $p$ is prime.
• Euler’s phi function $\phi(n)$ counts how many numbers up to $n$ are coprime to $n$.
• Euler’s theorem extends the power-remainder idea to many composite moduli.

So if you know Fermat’s Little Theorem, Euler’s theorem should feel like a bigger version of the same pattern. Both theorems tell us that powers can cycle in modular arithmetic. The difference is that Euler’s theorem needs $\phi(n)$ and the condition $\gcd(a,n)=1$.

This is why Euler’s theorem is often used in modular arithmetic problems involving large exponents, especially when the modulus is not prime 📊.

Common mistakes to avoid

When using Euler’s theorem, students, there are a few important things to check:

1. Make sure $a$ and $n$ are coprime.

If $\gcd(a,n)\neq 1$, Euler’s theorem does not apply directly.

1. Find $\phi(n)$ correctly.

A mistake in counting coprime numbers will lead to the wrong remainder.

1. Reduce the exponent carefully.

Write the exponent as a multiple of $\phi(n)$ plus a remainder.

1. Do not assume the result is always $1$.

Euler’s theorem gives $a^{\phi(n)}\equiv 1 \pmod n$, but if the exponent is not exactly a multiple of $\phi(n)$, you still need to work with the leftover power.

For example, if $\phi(n)=8$ and the exponent is $14$, then $14=1\cdot 8+6$, so you reduce to $a^6$, not to $1$.

Why the theorem is useful in real problem solving

Euler’s theorem is a problem-solving shortcut. In many exams and calculations, you may face expressions like $a^{1000}$ modulo some number. Direct calculation would be impossible by hand, but Euler’s theorem turns the problem into a smaller one.

It is especially useful in:

• finding remainders of large powers,
• simplifying modular arithmetic expressions,
• understanding repeating patterns in powers,
• building toward more advanced topics in number theory and cryptography 🔐.

The theorem also helps explain why modular arithmetic is structured and predictable rather than random.

Conclusion

Euler’s theorem is a major result in number theory that tells us how powers behave modulo $n$ when the base and modulus are coprime. The theorem states that if $\gcd(a,n)=1$, then

$$a^{\phi(n)}\equiv 1 \pmod n$$

The function $\phi(n)$ counts the numbers up to $n$ that are coprime to $n$, and this value controls the repeating pattern of remainders. Euler’s theorem extends Fermat’s Little Theorem from prime moduli to many composite moduli, making it a central idea in the Fermat and Euler topic.

students, if you can find $\phi(n)$, check coprimality, and reduce large exponents correctly, you can use Euler’s theorem to solve many modular arithmetic problems efficiently ✅.

Study Notes

• Euler’s theorem applies when $\gcd(a,n)=1$.
• The theorem is $a^{\phi(n)}\equiv 1 \pmod n$.
• $\phi(n)$ counts the integers from $1$ to $n$ that are coprime to $n$.
• If $n$ is prime, then $\phi(n)=n-1$.
• Euler’s theorem generalizes Fermat’s Little Theorem.
• To solve remainder problems, find $\phi(n)$, rewrite the exponent using multiples of $\phi(n)$, and simplify.
• Always check the coprime condition before applying the theorem.
• Euler’s theorem is useful for large powers and modular arithmetic patterns.