Application of Euler's theorem apart from finding last digits of huge numbers

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

• RSA Cryptosystem

• Pseudoprimes

• The Pollard $p-1$ Factoring Algorithm