0
$\begingroup$

I will not post the entire proof here. Just one part of the proof that they seem to use, then it will be simpler for you to read.

They use that

All the elements of $\mathbb{Z}_n$ that are relatively prime to n, form a group with operation multiplication modulo n. Let c be the order of this group, that is the number of elements in the group.

Then they say that $b^c =1$(mod n).

But why is this? If the group was cyclic I would have seen it, but the group may not be cyclic? I only need help with the statement in bold text, not all the info before that.

$\endgroup$
5
  • $\begingroup$ It doesn't have to be cyclic, the fact is the order of any element divides the order of the group. $\endgroup$
    – Gregory Grant
    Commented Mar 11, 2015 at 20:19
  • $\begingroup$ @GregoryGrant Yes, but why does b have to have order c then? $\endgroup$
    – user119615
    Commented Mar 11, 2015 at 20:20
  • $\begingroup$ And how do we know that b does not have order lower then c, for instance that the order may be c/2, so that still $b^c=1$(mod n). $\endgroup$
    – user119615
    Commented Mar 11, 2015 at 20:21
  • 1
    $\begingroup$ It can have order lower than $c$, but it still works. Suppose the order of $b$ is $a$. Then there is a $d$ s.t. $c=ad$ (because the order of an element divides the order of the group). Therefore $b^c=(b^a)^d=(\overline{1})^d=\overline{1}$. $\endgroup$
    – Gregory Grant
    Commented Mar 11, 2015 at 20:22
  • $\begingroup$ @GregoryGrant Thanks, I am so slow hehe! $\endgroup$
    – user119615
    Commented Mar 11, 2015 at 20:25

1 Answer 1

Reset to default
0
$\begingroup$

HINT:

The totient function $\phi(k)$ (number of integers less than $k$ that are relatively prime to $k$) is multiplicative: $\phi(ab) = \phi(a)\phi(b)$. That tells you something about the order of the group.

$\endgroup$
1
  • $\begingroup$ Moving this from comment to answer since the OP seems to be happy with it. It can have order lower than $c$, but it still works. Suppose the order of $b$ is $a$. Then there is a $d$ s.t. $c=ad$ (because the order of an element divides the order of the group). Therefore $b^c=(b^a)^d=(\overline{1})^d=\overline{1}$. $\endgroup$
    – Gregory Grant
    Commented Mar 11, 2015 at 20:27

You must log in to answer this question.

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