if $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots p_r^{a_r}$


$\lambda(n) = lcm[(p_1-1)(p_1^{a_1-1}),(p_2-1)(p_2^{a_2-1}),(p_3-1)(p_3^{a_3-1}),\dots,(p_r-1)(p_r^{a_r-1})]$


$k^{\lambda{n}} \equiv 1(\mod{n}) $

for all $k$ such that $gcd(k,n) = 1 $

where $p_1,p_2,p_3,\dots,p_n$ are prime numbers and $\lambda(n)$ is Carmichael function

please provide a proof for the above Carmichael theorem


By Euler's Theorem, $k^{\varphi(p_i^{a_i})}\equiv 1\pmod{p_i^{a_i}}$. Note that $\varphi(p_i^{a_i})$ divides $\lambda(n)$. It follows that $k^{\lambda(n)}\equiv 1\pmod{p_i^{a_i}}$ for all $i\le r$, and therefore $k^{\lambda(n)}\equiv 1\pmod{n}$.

Remark: The definition given in the OP is not quite the usual definition of the Carmichael function, and is not equivalent to it. (Everything is fine except for the prime $2$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.