1
$\begingroup$

I've seen this question. I'm trying to find the connection between Euler's totient function and Carmichael's function.

Carmichael's function outputs smallest $k$ such that:

$a^k ≡ 1 \pmod n$

Euler's totient function outputs the order of numbers $h$ less than some number $n$ that are coprime to $n$:

$gcd(h, n) = 1$

There exists Fermat's little theorem, stating that if there is some prime number $p$:

$a^{p-1} ≡ 1 \pmod p$

I'm thinking that i found the purpose of Carmichael's function while proving this theorem using Lagrange's theorem.

As we know, according to number theory, the congruence classes coprime to $n$ form a multiplicative group of integers modulo n, thus $∃ G = (ℤ/pℤ)^*$. Let's say there also exists a monoid subgroup $H$ generated by some element $a$ (this makes $H$ a cyclic group). According to the group theory, the order of $H$ is smallest $k$ such that $a^k ≡ e \pmod p$, where $e$ is identity element (and we know, that for groups under multiplication, identity element is always equal to $1$), and thus: $|H|$ = $λ(n)$. Finally we can prove theorem by knowing that according to Lagrange's theorem, the order subgroup $H$ divides the order group $G$, and that there exists $m$ such that $|H|=p-1=k*m$, therefore:

$a^{p-1} ≡ (a^k)^m ≡ 1^m ≡ 1 \pmod p$

But what's interesting here, is that somehow Carmichael's function happens to be subgroup of Euler's totient function. Is this because every multiplicative group has $λ(n)$ as its order?

Euler's theorem is generalisation of Fermat's little theorem stating that:

$a^{\phi(n)} ≡ 1 \pmod n$

We also know that there is some specific relationship between Carmichael's function and Euler's totient function, and somehow if this relationship is satisfied, multiplicative group becomes cyclic. Is there any proof to this relationship?

Do all subgroups of groups have exponent of groups as their order?

Thus is this the main purpose for existence of $λ(n)$ in cryptography? Does Carmichael's function only work because Totient function is its multiple? Why is output Carmichael's of Carmichael's function different from the output of Totient Function sometimes?

Or just how is Carmichael's function connected to Euler's totient function?

Thank you!

$\endgroup$
9
  • 1
    $\begingroup$ The Carmichael function allows to generalize the Euler-theorem. It is a bit more complicated because we cannot always reduce modulo $\lambda(n)$. If the modulus is coprime to the base, this can be done. In this case, the numbers $1,a,a^2,\cdots,a^{\lambda(n)}$ actually form a subgroup of the group consisting of $1,a,a^2,\cdots,a^{\phi(n)}$ $\endgroup$
    – Peter
    Commented Jan 23, 2018 at 18:22
  • 1
    $\begingroup$ The Carmichael-function cannot exceed the totient-function because it determines the smallest exponent with the desired congruence, hence it must be a divisor of the totient-function with the same argument. In short, we have $\lambda(n)|\phi(n)$ for all $n$. Equality is possible. $\endgroup$
    – Peter
    Commented Jan 23, 2018 at 18:32
  • 1
    $\begingroup$ An example is a number of the form $2^k$ with $k\ge 3$. We have $\phi(2^k)=2^{k-1}$, but $\lambda(2^k)=2^{k-2}$ $\endgroup$
    – Peter
    Commented Jan 23, 2018 at 18:44
  • 2
    $\begingroup$ We have equality if and only if the multiplicative group of $\mathbb Z_n^*$ is cyclic. This is the case, if and only if $n$ is an odd prime power (possibly an odd prime number) , twice an odd prime power (possibly twice an odd prime) or one of the numbers $1,2,4$. $\endgroup$
    – Peter
    Commented Jan 23, 2018 at 18:47
  • 2
    $\begingroup$ Euler's function $\phi(n)$ gives the order of the multiplicative group $(\mathbb{\Z}/n\mathbb{\Z})^×$, whereas Carmichael's function gives the exponent of this group, see fifth and sixth sentence of en.wikipedia.org/wiki/Torsion_group . $\endgroup$
    – j.p.
    Commented Jan 23, 2018 at 22:00

1 Answer 1

Reset to default
2
$\begingroup$

Let $U(n)$ be the group of units mod $n$.

Euler's totient function gives the order of $U(n)$. Euler's theorem is Lagrange's theorem for $U(n)$.

Carmichael's function gives the exponent of $U(n)$, by definition.

Every finite abelian group $A$ contains a cyclic subgroup whose order is the exponent of $A$. This subgroup correspond to the largest invariant factor of $A$.

$\endgroup$
4
  • $\begingroup$ Thank you, but does group have to be abelian to have a subgroup with order of exponent of group? In proof i pick G as a multiplicative group (and as i know, element operations there are not commutative, but associative). $\endgroup$
    – ShellRox
    Commented Jan 24, 2018 at 3:48
  • 4
    $\begingroup$ @ShellRox: The alternating group $A_5$ has exponent $30$, but no subgroup of this order. $\endgroup$
    – j.p.
    Commented Jan 24, 2018 at 7:05
  • $\begingroup$ @j.p Thank you! What about multiplicative group of integers modulo $n$, It seems to be monoid group (not abelian) but does have subgroup with the order of exponent of group. Does this mean that monoid groups can have these groups as well? $\endgroup$
    – ShellRox
    Commented Jan 24, 2018 at 10:17
  • $\begingroup$ Apologies for misunderstanding, I've read your link completely and understood that every finite group has exponent. Finally, $\phi{(n)}$ is the order of all multiplicative groups under $\pmod n$ correct? or just generally all multiplicative groups? $\endgroup$
    – ShellRox
    Commented Jan 24, 2018 at 10:53

You must log in to answer this question.

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