How many units in ring $\mathbb{Z}_{2^n}$?

Question

How many units in ring $\mathbb{Z}_{2^n}$? An unit of a ring is an element which has a multiplicative inverse. I have figured it out that for $n = 1$, the ring has only one unit (1). For $n = 2$, it has two units (1 and 3). How is next? Can I say that every odd numbers here will be a unit for that ring, because the even numbers here will product the even numbers themselves and never result 1 as the identity of the ring in multiplicative operation? That's mean the units of that ring is $2^{n-1}$, is not it?

Answer 1

Correct. In general, in $\mathbb Z_n$ the units are all elements coprime with $n$, and the number of those is given by Euler's totient function $\varphi$: https://en.wikipedia.org/wiki/Euler%27s_totient_function.

Proof: $k$ is a unit if and only if it has an inverse $l$ such that $kl=1$ in $\mathbb Z_n$. This is equivalent to a statement in $\mathbb Z$ that there exists $l,m$ such that $kl+nm=1$. Now:

• $k,n$ coprime: the existence of $l,m$ is a well-known fact (Bézout's identity) that is proven using Euclidean algorithm (https://en.wikipedia.org/wiki/Euclidean_algorithm#B%C3%A9zout%27s_identity)
• $k, n$ not coprime: then $\gcd(k,n)\gt 1$ would divide both $k$ and $n$ so if such $l,m$ existed it would also divide $kl+nm=1$ - a contradiction.