0
$\begingroup$

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)$

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

1 Answer 1

Reset to default
1
$\begingroup$

Since $\gcd(n-1,n)=1$, so $n-1 \in U(n)$ and order of $n-1$ is..?

$\endgroup$
4
  • $\begingroup$ It's a generator, so $|n-1| = |U(n)|$ right? I'm unsure what to do with that.. $\endgroup$
    – Zaya
    Oct 30, 2018 at 16:56
  • $\begingroup$ @Zaya Why don't you try a concrete example? Is $5-1$ a generator of $U(5)$? $\endgroup$
    – Erick Wong
    Oct 30, 2018 at 16:57
  • 1
    $\begingroup$ Ooooh, i see. Thank you. I see how it works. I'll update when I figure out why haha $\endgroup$
    – Zaya
    Oct 30, 2018 at 17:00
  • 1
    $\begingroup$ Better yet, think of it as $-1$ and just square it. $\endgroup$
    – Randall
    Oct 30, 2018 at 17:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .