Let $p$ and $q$ be two primes such that $p \nmid q-1 $ and $ q \nmid p-1$ (note that these two hypotheses could be superflous, but this is the context given by Paillier cryptosystem) and let $n = pq$. Prove that any element $g \in(\mathbb{Z}/n^2\mathbb{Z})^\times$ of order $n$ is of the form $g = 1 + kn$ with $\gcd(k,n) = 1$.
The reason behind this question is that I encountered this exercise while studying Paillier Cryptosystem. In the exercise was indeed asked firstly to prove that an element $g = 1 + kn$ with $\gcd(k,n) = 1$ has order exactly $n$, after that was asked to prove that every element of order $n$ can be written in that form. I was able to prove the first part considering binomial theorem and the fact that all terms vanish modulo $n^2$ except 1. But I did not figure out a way to prove the second part yet. I looked already for an answer but I could not find anything. Helpful hints or solution would be much appreciated.
I will give you a hint. Given condition on $p,q$ implies that $\varphi(n) = (p-1)(q-1)$ and $n = pq$ are relatively prime. If $g\in(\mathbb{Z}/n^2\mathbb{Z})^\times$ is such that $g^n \equiv 1\bmod n^2$, then this necessarily means $g^n\equiv 1\bmod n$ obviously.
Now Euler's Theorem says $g^{\varphi(n)}\equiv 1\bmod n$ and you can now do a Euclidean Algorithm on the exponents to conclude that $g\equiv 1\bmod n.$