4 ms·
Is there an "intuitive explanation" for the part "λ(n) is a number such that x^λ(n) ≡ 1 (mod n) for any x such that gcd(x, n) = 1. From this you can conclude th
by thrdbndndn 5y ago
Is there an "intuitive explanation" for the part "λ(n) is a number such that x^λ(n) ≡ 1 (mod n) for any x such that gcd(x, n) = 1. From this you can conclude that x^a ≡ x^b (mod n) if a ≡ b (mod λ(n))", or a formal name for such "λ(n)" so I can search around?
I find it quite hard to grasp.
- _hl_ 5y agoFermat's little theorem. I'm not aware of an intuitive explanation unfortunately.
- thrdbndndn 5y agoAfter reading about it, I assume the λ(n) here is the Euler's totient function. I think the author probably should give the definition of the function first, and then say it fits the equation "x^λ(n) ≡ 1 (mod n) for any x such that gcd(x, n) = 1" due to the theorem, insteads of the other way around (λ(n) is a number that match this equation). (Also, it probably is more intuitive to say "x^λ(n) - 1 is a multiple of n" than "x^λ(n) ≡ 1 (mod n)".)
- enedil 5y agoλ(n) isn't the totient. As it was told, it's the Carmichael function.
- cryvate1284 5y agoCarmichael's Function is the name. https://en.m.wikipedia.org/wiki/Carmichael_function https://en.m.wikipedia.org/wiki/Carmichael_function