Carmichael function: Difference between revisions

Revision as of 23:15, 12 January 2022

Revision as of 10:33, 13 January 2022

Line 94:

:<math>a^r = 1^k \cdot a^r \equiv \left(a^{\lambda(n)}\right)^k\cdot a^r = a^{k\lambda(n)+r} = a^m \equiv 1\pmod{n}</math>

for all numbers {{mvar | a}} coprime with {{mvar | n}}. It follows {{math | 1=''r'' = 0}}, since {{math | ''r'' < ''λ''(''n'')}} and {{math | ''λ''(''n'')}} the minimal positive such number.

===Extension for powers of two===

For {{mvar | a}} coprime to (powers of) 2 we have {{math | ''a'' {{=}} 1 + 2''h''}} for some {{mvar | h}}. Then,

:<math>a^2 = 1+4h(h+1) = 1+8C</math>

where we take advantage of the fact that {{math | ''C'' :{{=}} {{sfrac|(''h'' + 1)''h''|2}}}} is an integer.

So, for {{math | 1=''k'' = 3}}, {{mvar | h}} an integer:

:<math>\begin{align}

a^{2^{k-2}}&=1+2^k h \\

a^{2^{k-1}}&=\left(1+2^k h\right)^2=1+2^{k+1}\left(h+2^{k-1}h^2\right)

\end{align}</math>

By induction, when {{math | ''k'' ≥ 3}}, we have

:<math>a^{2^{k-2}}\equiv 1\pmod{2^k}.</math>

It provides that {{math | ''λ''(2^''k'')}} is at most {{math | 2^{''k'' − 2}}}.<ref name="car">{{cite book|first=Robert Daniel|last=Carmichael|title=The Theory of Numbers|___location=Nabu Press|isbn=1144400341|url=http://www.gutenberg.org/ebooks/13693}}{{page needed|date=May 2020}}</ref>

=== {{math | ''λ''(''n'')}} divides {{math | ''φ''(''n'')}} ===

Line 155 ⟶ 136:

:<math>a \equiv a^{\lambda(n)+1} \pmod n.</math>

===Extension for powers of two===

For {{mvar | a}} coprime to (powers of) 2 we have {{math | ''a'' {{=}} 1 + 2''h''}} for some {{mvar | h}}. Then,

:<math>a^2 = 1+4h(h+1) = 1+8C</math>

where we take advantage of the fact that {{math | ''C'' :{{=}} {{sfrac|(''h'' + 1)''h''|2}}}} is an integer.

So, for {{math | 1=''k'' = 3}}, {{mvar | h}} an integer:

:<math>\begin{align}

a^{2^{k-2}}&=1+2^k h \\

a^{2^{k-1}}&=\left(1+2^k h\right)^2=1+2^{k+1}\left(h+2^{k-1}h^2\right)

\end{align}</math>

By induction, when {{math | ''k'' ≥ 3}}, we have

:<math>a^{2^{k-2}}\equiv 1\pmod{2^k}.</math>

It provides that {{math | ''λ''(2^''k'')}} is at most {{math | 2^{''k'' − 2}}}.<ref name="car">{{cite book|first=Robert Daniel|last=Carmichael|title=The Theory of Numbers|___location=Nabu Press|isbn=1144400341|url=http://www.gutenberg.org/ebooks/13693}}{{page needed|date=May 2020}}</ref>

===Average value===