I've been trying to understand the group theory proof of Fermat's little theorem.

Let's say there exists group $G = (ℤ/pℤ)^x$, and it has multiplicative subgroup $H$ (a monoid group, as i understand). The group $H$ is generated by some element $a$, this makes $H$ a cyclic group.

According to group theory, $|H|$ is the smallest positive integer $k$ such that $a^k = e$ (where $e$ is identity) and considering that identity in multiplicative group is always $1$, we can assume that order of the subgroup $|H|$ is equal to output of Carmichael's function. Thus $a^k ≡ 1 mod(p)$.

Now as i understand, $|H|≡λ(p)$, if $H$ is multiplicative group, is this always a case? If so, why?

  • $\begingroup$ this is confusing. Are you asking if, for composite $n$, we always have $\lambda (n) = |\,\left( \mathbb Z/n\mathbb Z\right)^*\,|$ or are you asking something else? $\endgroup$ – lulu Jan 19 '18 at 16:06
  • $\begingroup$ If I have interpreted your question properly (not at all clear) then you can read about the Carmichael Function to find many cases in which $\lambda (n)< \varphi(n)$. $\endgroup$ – lulu Jan 19 '18 at 16:07
  • $\begingroup$ @lulu According to the group theory, If is generated by some element $a$, the the order of $H$ is also the order of $a$. i.e it is the smallest positive integer $k$ such that $a^k = e$ (where $e$ is identity, and as we know identity under multiplicative group is always 1), and thus $a^k = 1 mod (p)$, isn't this similar to Carmichael's function? $\endgroup$ – ShellRox Jan 19 '18 at 16:23
  • 1
    $\begingroup$ Your question is a jumble. You start with a prime modulus, for which the multiplicative group is cyclic. Obviously in this case $\lambda (p)=\varphi (p)=p-1$, no problem. Then you switch to $n$ but you don't tell us what $n$ is. If it is meant to be composite, then you can not assume that $\left( \mathbb Z/n\mathbb Z \right)^*$ is cyclic, it isn't always. So, please edit your post to make your assumptions and your question clearer. $\endgroup$ – lulu Jan 19 '18 at 16:28
  • 1
    $\begingroup$ The header still refers to $n$ and you never actually say that $p$ is a prime, but let's take for granted that it is. In that case, it is indeed true that $ \left( \mathbb Z/p\mathbb Z \right)^*$ is cyclic. It has order $p-1$ of course and in this case it is certainly true (and somewhat obvious) that we also have $\lambda (p)=p-1$. In general, $\varphi(n)$ is the order of $\left( \mathbb Z/n\mathbb Z \right)^*$ so here $\varphi(p)=p-1=\lambda (p)$. However, this is not generally true if you replace $p$ with a composite number $n$. $\endgroup$ – lulu Jan 19 '18 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.