2
$\begingroup$

I am looking for clever applications of Euler's Theorem. On browsing the internet, I see that nearly all the applications of the theorem asks for finding last few digits of a huge number. The only other application I could find was Euler's Proof of Fermat's theorem on sums of two squares. which uses Fermat's little theorem ( A weaker form of Euler's totient Theorem) and infinite descent.

This makes me wonder if we could find more uses for the theorem?

PS: I am interested in undergraduate level theorems/problems which could be solved using Euler's theorem (along with other technique, if necessary) Please mention suitable hints along with your problem.

$\endgroup$
1
$\begingroup$

I can think of one possible example. As $\phi(m)$ is the number of natural numbers less than $m$ which are coprime to $m$, Euler's theorem provides a good upper bound to a lot of problems which involve coprime numbers.

For example, if we consider the problem of Quadratic Congruence, solving the equation $x^{2} \equiv a\ (mod\ p)$, where p is a prime. Solving this problem using a number of algorithms require finding a non-residue $z$ of p first. It can be shown that there are $\phi(\phi(m))$ quadratic residues for m, hence the probability of finding a non-quadratic residue for a given p is quite high in practice. Even, for a composite $m$, checking if $a$ is a quadratic residue of $m$ uses the following criteria, which is based on Euler's theorem:

Euler's Criterion: The equation $x^{2} \equiv a \ (mod\ m)$ has a solution if and only if

$a^{\frac{\phi(m)}{2}} \equiv 1 \ (mod\ m)$

As another example, I'd like to say that, finding a primitive root modulo $m$ has also a good use of Euler's theorem, the testing for primitive-rootness modulo $m$ exploits Euler's theorem and Lagrange's theorem equally.

$\endgroup$
1
$\begingroup$

This application is maybe not for undergrads, but if you take Hensel's lemma for granted, it's a nice application, in my opinion.

Hensel's lemma: Let $f(t)$ be a polynomial with coefficients in $\mathbb{Z}_p$ (the $p$-adic integers, $p$ prime). If there exists $a\in\mathbb{Z}_p$ such that $f(a)\equiv0\pmod{p}$ and $f'(a)\not\equiv0\pmod{p}$, then there exists an unique $b\in\mathbb{Z}_p$ such that $f(b)=0$ and $a\equiv b\pmod{p}$.

From this follows that there exist $p-1$ different elements $\theta$ in $\mathbb{Z}_p$ such that $\theta^{p-1}=1$: these are the roots of unity.

To prove this, take $f(t)=t^{p-1}-1$ and $a$ integer with $1\leq a\leq p-1$. From Eulers theorem it follows that $f(a)\equiv0\pmod{p}$ from which a root of unity in $\mathbb{Z}_p$ follows.

$\endgroup$
0
$\begingroup$

An important application of Euler's Theorem is the RSA Cryptosystem. See the paper A Modern Day Application of Euler’s Theorem: The RSA Cryptosystem by M. Maxey for some information about it.

You may also find some helpful information in A Concrete Introduction to Higher Algebra by L.N. Childs. The chapter $10$ Applications of Euler’s Theorem is subdivied into three sections

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.