Content deleted Content added
Changing short description from "function of interest in number theory" to "Function in mathematical number theory" (Shortdesc helper) |
→Numerical example: Added an extended example, to show more detail of the Charmichael function algorithm. Tags: Mobile edit Mobile web edit |
||
Line 58:
==Numerical example==
Carmichael's function at 8 is 2, {{math | ''λ''(8) {{=}} 2}}, because for any number {{mvar | a}} coprime to 8 it holds that {{math | ''a''<sup>2</sup> ≡ 1 (mod 8)}}. Namely, {{math | 1<sup>2</sup> {{=}} 1 (mod 8)}}, {{math | 3<sup>2</sup> {{=}} 9 ≡ 1 (mod 8)}}, {{math | 5<sup>2</sup> {{=}} 25 ≡ 1 (mod 8)}} and {{math | 7<sup>2</sup> {{=}} 49 ≡ 1 (mod 8)}}. Euler's [[totient function]] at 8 is 4, {{math | ''φ''(8) {{=}} 4}}, because there are 4 numbers less than and coprime to 8 (1, 3, 5, and 7). [[Euler's theorem]] assures that {{math | ''a''<sup>4</sup> ≡ 1 (mod 8)}} for all {{mvar | a}} coprime to 8, but 4 is not the smallest such exponent.
<h3>Extended Example</h3>
Carmichael's function at 5 is 4, {{math | ''λ''(5) {{=}} 4}}, because for any number {{mvar | a}} coprime to 5 => (1, 2, 3, 4), where {{mvar | m}} {{=}} 2, it '''does not hold''' that {{math | ''a''<sup>''m''</sup> ≡ 1 (mod 5)}}. Namely, {{math | 1<sup>2</sup> {{=}} 1 (mod 5)}}, {{math | 2<sup>2</sup> {{=}} 4 !≡ 1 (mod 5)}}, {{math | 3<sup>2</sup> {{=}} 9 !≡ 1 (mod 5)}} and {{math | 4<sup>2</sup> {{=}} 16 ≡ 1 (mod 5)}}. Because at least one equation is not modular congruent (!≡); therefor increase ''m''.
When {{math | ''m'' {{=}} 3}} there is at least one equation were modular congruence does not hold. Namely {{math | 1<sup>3</sup> {{=}} 1 (mod 5)}}, {{math | 2<sup>3</sup> {{=}} 8 !≡ 1 (mod 5)}}, {{math | 3<sup>3</sup> {{=}} 27 !≡ 1 (mod 5)}} and {{math | 4<sup>3</sup> {{=}} 64 !≡ 1 (mod 5)}}.
But modular congruence is true for all coprime of 5 => (1,2,3,4), when ''m'' {{=}} 4. Namely {{math | 1<sup>4</sup> {{=}} 1 (mod 5)}}, {{math | 2<sup>4</sup> {{=}} 16 ≡ 1 (mod 5)}}, {{math | 3<sup>4</sup> {{=}} 71 ≡ 1 (mod 5)}} and {{math | 4<sup>4</sup> {{=}} 256 ≡ 1 (mod 5)}}.
== Computing {{math | ''λ''(''n'')}} with Carmichael's theorem ==
| |||