Νumber of irreducible elements in $\Bbb Z_n$ The number of irreducible elements in $\Bbb Z_{36}$ ? 
I was only able to eliminate 13 elements which were a zero and 12 units. Then I found the following facts : 
$(a)$ An element $[r]$ in $\Bbb Z_n$ is irreducible iff $\gcd(r,n)=p$, where $p$ is a prime integer. 
$(b)$ The number of irreducible elements in $\Bbb Z_n$ is 
$\psi(n)=\sum_{p|n}\phi \big(\frac np \big)   $ where the sum runs over the prime divisors of n.
However I have not seen the proof anywhere. For $(a)$, I tried the following:
Since $\gcd(r,n)=p$ , then $rx+ny=p$ for some $x,y \in \mathbb{Z}$.
If possible, let $[r]=[u][v]$ for some non-units $[u],[v]$ in $\Bbb Z_n$, then how to show a contradiction ??
Any help or suggestions is appreciated. Thanks for your time.
 A: Since $\mathbb{Z}_n$ is not a domain there are irreducible elements which are not prime. The proper result is that an element 

$[a]$ in $\mathbb{Z}_n$ is irreducible iff $(a,n)=p$ and $p^{2} \mid n$. 

Let's prove it:
Let $a\in\mathbb{Z}_n$ such that $(a,n)\ne 1$ and $n\nmid a$ because it is both a nonzero and nonunit element being irreducible. We can have three cases:
1) There are  two primes $p$ and $q$ (that can also be the same $p=q$) such that $pq \mid(a,n)$.
In this case we can let $a=bc$ where $p \mid b $ and $q \mid c$ and so we can see that $[a]$ is the product of nonzero nonunit elements ($[b],[c]$) so it is not irreducible.
2) There is a prime $p$ such that $(a,n)=p$ and also $p^{2} \nmid n$.
In this case we have $(n,p^{2})=p$ and $p \mid a$, so there are two integers  $r,s$ (Bezout) such that $a=nr+p^{2}s$. So $[a]=[p][sp]$ which are nonzero nonunit elements so again $[a]$ is not irreducible.
3) There exists a prime $p$ such that $(a, n) = p$ and $p^{2} \mid n$.
In this case we show that $[a]$ is irreducible.
Let $[b], [c] \in \mathbb{Z}_n$ and $[a] = [b][c]$. Then there is an integer $k$ such that $a = bc + kn$. By hypothesis (irreducibility of $[a]$), $p \mid bc$ and so $p$ must divide at least one of $b, c$. It cannot divide both, else, since $p^{2} \mid n$ we would have $p^{2} \mid a$ a contradiction. Let us say $p \mid b$ and $p \nmid c$ (the other way is symmetric). Now if there exists a prime $q \ne p$, then $q \nmid c$, for $(a, n) = p$. Thus $(c, n) = 1$ and so $[c]$ is a unit.
This ends the proof.
