# Prove if $n>2$ then $2 | |U(n)|$

Here's what I have so far, but I'm not sure how to bridge that last step into the rest of the proof. I just need to prove there always exists some member of $$U(n)$$ with cardinality 2. I'm not sure how.

By the definition of cyclic groups, any member of $$U(n)$$ is also a generator of a cyclic sub-group.
Pick a member, $$x$$ from $$U(n)$$.
We know $$|x|$$ divides $$|U(n)|$$ by Lagrange's theorem.
???
So if $$2$$ divides $$|x|$$ then two divides $$U(n)$$

EDIT: Thank you guys, I figured it out:

By the definition of cyclic groups, any member of $$U(n)$$ is also a generator of a cyclic sub-group.
Because $$gcd(n-1, n)$$ is always $$1$$, we know $$n-1 \in U(n)$$.
$$(n-1)^2=n^2+1$$
$$(n^2+1)\ mod\ n = 1$$
Therefore $$|n-1| = 2$$.
Because the group generated by $$n-1$$ is a subgroup, by Lagrange's theorem if $$2|(n-1)$$ then $$2|U(n)$$

• You need a non-identity element $x$ with $x^2=1$. Can you find one? Commented Oct 30, 2018 at 16:51

Since $$\gcd(n-1,n)=1$$, so $$n-1 \in U(n)$$ and order of $$n-1$$ is..?
• It's a generator, so $|n-1| = |U(n)|$ right? I'm unsure what to do with that..
• @Zaya Why don't you try a concrete example? Is $5-1$ a generator of $U(5)$? Commented Oct 30, 2018 at 16:57
• Better yet, think of it as $-1$ and just square it. Commented Oct 30, 2018 at 17:02