How to find an element of order 30 in the multiplicative group of $\Bbb Z_{900}$?

Question

I need to find at least one element which has order $30$ in the multiplicative group of $\Bbb Z_{900}$. I'm following this approach but not really understood how to apply correctly the CRT to set the three congruences. In particular, I don't understand why the order of a is a divisor of 2 etc. Can anyone explain me better how to apply the CRT to this problem? Thank you.

Answer 1

For any $n\ge2$, $1+n$ has multiplicative order $n$ modulo $n^2$. Just observe that $$(1+n)^k\equiv 1+kn\pmod{n^2}.$$

Answer 2

We have $$900=2^2\times 3^2\times 5^2$$

If $\gcd(n,900)=1$ then the order of $n\pmod {900}$ is the lcm of its orders $\pmod {2^2,3^2,5^2}$.

We start $n\equiv 2 \pmod {25}$. Direct computation shows that this has order $20$, so $4$ has order $10\pmod {25}$.

Now, $4$ has order $3\mod 9$, and let's just take $n\equiv 1 \pmod 4$.

Then we just need to solve $$n\equiv 1 \pmod 4 \quad \& \quad n\equiv 4\pmod {225}$$

Easy to see that $\boxed {n\equiv 229 \pmod {900}}$ works.

Another approach is simple trial and error. That method quickly gets us to $n=11$ as a smaller solution.