Hacker News Reader

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.

View on HN

Carmichael's Function is the name.

https://en.m.wikipedia.org/wiki/Carmichael_function

Fermat's little theorem. I'm not aware of an intuitive explanation unfortunately.

After 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)".)

λ(n) isn't the totient. As it was told, it's the Carmichael function.

Reply on news.ycombinator.com