Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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