<s>[INST] How many invertible elements are there in $\mathbb {Z_ {990}}$ and $\mathbb {Z_ {1060}}$. How many invertible elements are there in $\mathbb {Z_ {990}}$ and $\mathbb {Z_ {1060}}$ . Justify your answer.
Hello, could someone explain to me how to find the invertible elements of a set as large as $\mathbb {Z_ {990}}$ and $\mathbb {Z_ {1060}}$
I thought about putting together the set and trying each one but it is very big and it can take forever
 [/INST] For $k$ to be invertible in $\mathbb Z_n$ means there is an integer $a$ so that $ak \equiv 1 \pmod n$.  And $ak\equiv 1\pmod n$ means there is an integer $b$ so that $ak = 1+bn$ which means $ak -bn = 1$.
By Bezouts Lemma that is possible if and only if $k,n$ are relatively prime.
So find all the numbers $k$ so that $k$ and $990$ are relatively prime.
As $990 = 2\cdot 3^2\cdot 5\cdot 11$ this will mean find all the integers less than $990$ that are not a mulitple of $2,3,5$ or $11$.
.....
There is a function that counts the number of elements that are relatively prime to $n$ and less than $n$.  It is called the Euler Totient function.

$\phi(n) = $#of integers, $k: k< n; \gcd(k,n) = 1$.

There are some formulas I won't prove but:

*

*If $n = mp$ and $\gcd(m,p) = 1$ then $\phi(n) = \phi(m)\phi(n)$.

*If $p$ is prime $\phi(p) = p-1$.

*If $n =p^k$ and $p$ is prime $\phi(p^k)= p^{k-1}(p-1)$
From those we can conclude if If $n = \prod p_i^{k_i}$ then

$\phi(n) = \prod[p_i^{k_i-1}(p_k-1)] = n\prod\limits_{p\text{ prime};p|n}(1-\frac 1p)$.

So there are $\phi(990) = \phi(3^2)\phi(2)\phi(5)\phi(11) = 3^1\cdot 2\cdot 1\cdot 4\cdot 10 = 240$ such elements.
Or .... $990\prod (1-\frac 1p) = 990(1-\frac 12)(1-\frac 13)(1-\frac 15)(1-\frac 1{11})=$
$990\cdot \frac 12\cdot\frac 23\cdot\frac 45\cdot\frac {10}{11}=$
$445\cdot\frac 23\cdot\frac 45\cdot\frac {10}{11}=$
$330\cdot\frac 45\cdot\frac {10}{11}=$
$264\cdot\frac {10}{11}= 260$
...or ....
$\require{cancel}$
$990\cdot \frac 12\cdot\frac 23\cdot\frac 45\cdot\frac {10}{11}=$
$990\cdot \frac 1{\cancel 2}\cdot\frac {\cancel 2}3\cdot\frac 4{\cancel 5}\cdot\frac {\cancel{10}2}{11}=$
$990 \cdot \frac 8{33}=$
$30\cdot 8 = 240$.
</s>