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
 A: I will explain how to find the invertible elements of $\mathbb{Z}_n$.
An element $a$ is invertible in $\mathbb{Z}_n$ if and only if therte exists $b\in\mathbb{Z}_n$ such that $a\cdot b=1$, in other words $a\cdot b\equiv 1\pmod{n}$.
$0$ is clearly not invertible.
Observe that if $a$ is not relatively prime with $n$, then this is impossible, as $a\cdot b$ will always be divisible by $\gcd(a,n)$ so this would mean $\gcd(a,n)|1$.
So all elements not relatively prime woth $n$ are not invertible. What about the elements of $\mathbb{Z}_n$ which are relatively prime to $n$? Well let $a$ be one of them. Take the set $\{a,2a,3a,...,(n-1)a\}$. Suppose $ia\equiv ja$ for some $i$ and $j$. This means $a\cdot|i-j|$ is divisible by $n$ so because $a$ is relatively prime to $n$, then $|i-j|$ is divisible by $n$, but $n>|i=j|$ so $|i-j|=0$ so $i=j$.
Thus, all elements of $\{a,2a,3a,...,(n-1)a\}$ are distinct$\pmod{n}$ and there are no elements divisible by $n$ in the above set (because $a\neq 0$ and $a$ and $n$ are coprime), so in the above set there must be an element $\equiv 1\pmod{n}$, thus $a$ is invertible.
So the invertible elements in $\mathbb{Z}_n$ are all the numbers smaller than $n$, which are coprime to $n$. The number of such elements is $\varphi(n)$
A: Let $\varphi(n) = \{a\in \mathbb{Z}_n : a \text{ is invertible}\} = \{a\in \mathbb{Z}_n : \gcd(a,n) = 1\}.$
If $n=p_1^{e_1} \cdots p_s^{e_s}$ is the prime factorization of $n$, then (one can prove that) $$\varphi(n) = n\prod_{k=1}^{s}\Big(1-\dfrac{1}{p_k}\Big).$$
For $n=990,$ we have that $n=2\cdot3^2\cdot5\cdot11$, so $$\varphi(990)=990\cdot\Big(1-\dfrac{1}{2}\Big)\cdot\Big(1-\dfrac{1}{3}\Big)\cdot\Big(1-\dfrac{1}{5}\Big)\cdot\Big(1-\dfrac{1}{11}\Big)=240.$$
A: 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$.
