1
$\begingroup$

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$?

$\endgroup$
2
$\begingroup$

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.

$\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.