A proposition in my book states: $(\mathbb{Z}/n\mathbb{Z})^{\times} = \{a \in \mathbb{Z}/n\mathbb{Z}~|(a,n) = 1\}$ which I want to prove.
I start by defining $a$ in terms of prime factors $$a = p_1^{\alpha_1}p_2^{\alpha_2}...p_i^{\alpha_i} = \prod p_i^{\alpha_i}$$ and $$n = p_1^{\beta_1}p_2^{\beta_2}...p_i^{\beta_i} = \prod p_i^{\beta_i}$$
We have $n/ka$, $k$ is some multiple of $a$, as $\frac{ka}{n} = nq + r$
If $ka$ and $n$ have factors in common, the remainder $r$ will be $\geq $ the least common factor that isn't $1$. I don't really have any idea of how to prove this yet. Can I have some hints? I would prefer not to use a contradiction and instead show that by the process of dividing integers with common factors, a remainder that is 1 does not exist. Thank you
By definition, the elements of $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$ are the units of the ring $R = \mathbb{Z}/n\mathbb{Z}$. To say that $a\in R$ is a unit is to say that there exists $x\in R$ such that $ax = 1$, but by definition of $R$ that just means that $ax\equiv 1\pmod{n}$.
At this point you can write everything out in prime factors if you want, but I don't think this is more fundamental - you are relying on the fundamental theorem of arithmetic (no pun intended).
In any case, the statement $ax\equiv 1\pmod{n}$ is just saying that there exists some integer $y$ such that $ax = ny + 1$. Then you have that $ax - ny = 1$ which means that $\text{gcd}(a,n) = 1$; that's what you wanted to prove.
EDIT We need to also prove that if $(a,n) = 1$ then $a$ is a unit in $R$. But it is a Theorem (which you might try proving) that if $(a,n) = 1$ then there exist integers $x$ and $y$ such that $ax + ny = 1$, which implies that $ax\equiv 1\pmod{n}$ and thus $a$ is a unit in $R$.