Content deleted Content added
Removed superfluous wording from first sentence. Having "member of the set of positive integers" adds no clarity to the simpler "positive integer". |
→Carmichael's theorems: typo fixed |
||
Line 75:
{{anchor|Carmichael's theorem}}
Carmichael proved two theorems that, together, establish that if {{math | ''λ''(''n'')}} is considered as defined by the recurrence of the previous section, then it satisfies the property stated in the introduction, namely that it is the smallest positive integer {{mvar | m}} such that <math>a^m\equiv 1\pmod{n}</math> for all {{mvar | a}} relatively prime to {{mvar | n}}.
{{Math theorem |name=Theorem 1|math_statement=If {{mvar | a}} is relatively prime to {{mvar | n}} then <math>a^{\lambda(n)}\equiv 1\pmod{n}</math>.<ref>
This implies that the order of every element of the multiplicative group of integers modulo {{mvar | n}} divides {{math | ''λ''(''n'')}}. Carmichael calls an element {{mvar | a}} for which <math>a^{\lambda(n)}</math> is the least power of {{mvar | a}} congruent to 1 (mod {{mvar | n}}) a ''primitive λ-root modulo n''.<ref>Carmichael (1914) p.54</ref> (This is not to be confused with a [[primitive root modulo n|primitive root modulo {{mvar | n}}]], which Carmichael sometimes refers to as a primitive <math>\varphi</math>-root modulo {{mvar | n}}.)
{{Math theorem |name=Theorem 2|math_statement=For every positive integer {{mvar | n}} there exists a primitive {{mvar | λ}}-root modulo {{mvar | n}}. Moreover, if {{mvar | g}} is such a root, then there are <math>\varphi(\lambda(n))</math> primitive {{mvar | λ}}-roots that are congruent to powers of {{mvar | g}}.<ref>Carmichael (1914) p.55</ref>}}
| |||