# Euler Fermat Theorem with composites

Show that for every integer $a$ such that $\gcd(a,100)=1$, $a^{100}= 1 \mod 100$ and use this to compute the last two digits of $(11)^{102}$. Can you say something more precise about the order of an element in $(\mathbf{Z}/100 \mathbf{Z} )^*$?

So, I worked out that the if $S=(\mathbf{Z}/100 \mathbf{Z} )^*$ and $a$ is in $S$, then $aS=S$ because they're all coprimes. Thus for any element $x$ in $S$, $x^{40}=1 \mod 100$. But I can't understand why it works for $20$ when $40$ is the number of elements coprime to $100$.

Using the fact that $11^{20}=1 \mod 100$ its easy to see that $11^{102}= (11^{20})^5\cdot (11^2)=121 \mod 100=21$, but I'm still not sure why $20$ works.

Also, I don't know what I can say about elements of $(\mathbf{Z}/100 \mathbf{Z} )^*$ except that their order must be less than $20$?

-
For some basic information about writing math at this site see e.g. here, here, here and here. – Julian Kuelshammer Nov 25 '12 at 6:49

Let $a$ be relatively prime to $100$. By Euler's Theorem, $a^2\equiv 1\pmod{4}$. Again by Euler's Theorem, $a^{20}\equiv 1\pmod{25}$.

Note that $2$ divides $20$. It follows that $a^{20}\equiv 1\pmod{4}$. Since $a^{20}$ is congruent to $1$ modulo $4$ and modulo $25$, it follows that $a^{20}\equiv 1\pmod{100}$.

We cannot do better than $20$. It is a standard theorem that if $p$ is any odd prime, then for any positive $b$, there exists a primitive root modulo $p^b$, that is, an element of order $\varphi(p^b)$ modulo $p^b$. That there are elements of order $20$ modulo $25$, and hence modulo $100$, follows by taking $p=5$, $b=2$.

In general, suppose that we are looking for the least positive exponent $e$ such that $a^e\equiv 1\pmod{m}$ for every $a$ relatively prime to $m$. This $e$ is called the *least universal exponent for $m$. Its standard name is $\lambda(m)$, so we call it that from here on.

By Euler's Theorem, we have $\lambda(m) \le \varphi(m)$. If $m$ is a power of an odd prime, then $\lambda(m)= \varphi(m)$. But we can often do better than $\varphi(m)$. From here on assume $m$ is odd. Analysis for even $m$ is somewhat more complicated.

Let the odd number $m$ have prime power factorization $m=p_1^{d_1}\cdots p_k^{d_k}$. It is easy to see that the least common multiple of the $\varphi(p_i^{d_i})$. Is a universal exponent. It is in fact the least universal exponent $\lambda(m)$.

Note that $$\varphi(m)=\prod_{i=1}^k \varphi(p_i^{d_i}).$$ If $m$ has a fair number of prime divisors, $\lambda(m)$, the least common multiple of the $\varphi(p_i^{d_i})$, can be much smaller than $\varphi(m)$. This is partly because each of the $\varphi(p_i^{d_i})$ is divisible by a positive power of $2$, and we typically do not need all these $2$'s.

For more details, look under Carmichael Function.

-