Explain Carmichael's Function To A Novice
I understand that the Carmichael Function (I'm going to call λ) is essentially the smallest positive integer m, where $a^m$ is congruent $1 \pmod n$ for all $a$ co-prime to $n$ and less than $n$.
6 makes sense to me. The only co-prime is 5 and $5^2 = 25\equiv 1 \pmod 6$. So $λ(6) = 2$.
I also know that the answer to $λ(49)$ is $42$. I'm not clear on what the "shortcut" is though. I realized I could brute force the answer, but that's not feasible for any significant values of n. I understand there is some sort of mathematical "shortcut" to derive this answer... something to do with LCM of prime powers. I would appreciate an explanation on this shortcut in terms an avg 14 year old could understand. No Fermat or Euler.
The first thing we want is this:
If $\gcd(a,b) = 1$ and $a|bc$, then $a|c$.
This is fairly easy to establish. For example, you can use the Bezout identity: $a$ and $b$ are coprime if and only if there exist $x$ and $y$ such that $ax+by=1$. Multiplying through by $c$ we get $c = acx + bcy$. Since $a$ divides both $acx$ and $bcy$ (the latter by virtue of dividing $bc$), then $a$ divides $c$.
From this we have:
Suppose that $a$ and $n$ are coprime integers, and $x$ and $y$ are integers such that $ax\equiv ay\pmod{n}$. Then $x\equiv y\pmod{n}$.
Indeed, if $ax\equiv ay\pmod{n}$, the $n$ divides $ax-ay = a(x-y)$. Since $\gcd(n,a)=1$ by assumption, it follows that $n|x-y$, so $x\equiv y\pmod{n}$.
Hence, for each $a$ that is coprime to $n$, there is at least one positive integer $k$ such that $a^k\equiv 1\pmod{n}$:
If $\gcd(a,n)=1$, then there exists a positive integer $k$ such that $a^k\equiv 1\pmod{n}$.
There are only finitely many positive integers smaller than $n$ that are coprime to $n$. Let's say there are $t$ of them. Then the numbers $a\bmod n$, $a^2\bmod n$, $a^3\bmod n,\ldots, a^{t+1}\bmod n$ cannot all be distinct, because each of them is coprime to $n$, and there are $t+1$ of them, all smaller than $n$. So there must exist exponents $i$ and $j$, $i\lt j$, such that $a^i\equiv a^j\pmod{n}$. Write $j=i+\ell$, and we have $$a^i(1) \equiv a^ia^{\ell}\pmod{n}.$$ Since $\gcd(a^i,n)=1$, then we can cancel and we get $1\equiv a^{\ell}\pmod{n}$, which shows there must be some exponent that works.
If $a^k\equiv 1\pmod{n}$, and $r$ is a multiple of $k$, then $a^r\equiv 1\pmod{n}$.
This is fairly straightforward: we can write $r=kt$ for some $t$. Then using the laws of exponents, we have: $$a^r = a^{kt} = (a^k)^t \equiv 1^t \equiv 1\pmod{n}.$$
So, given a positive integer $n$, why does there exist a smallest $m$ such that $a^m\equiv 1\pmod{n}$ for every positive $a$ that is smaller than $n$ and coprime to $m$? First, note that there has to exist some $m$ that works: there are only finitely many positive integers coprime to $m$; call them $a_1,\ldots,a_f$. For each of them, we know there exists some positive integer $k_1$, $k_2,\ldots,k_f$, with the property that $a_i^{k_i}\equiv 1\pmod{n}$. Now, if $k=k_1k_2\cdots k_f$, then $k$ is a multiple of each $k_i$, so $a_i^k\equiv 1\pmod{n}$.
That is, there certainly are positive integers that "work" for all $a$ coprime to $n$, positive, and smaller than $n$. Since there are such integers, there must be a smallest one. That smallest one is the value of the Carmichael function.
Using the division algorithm, it is easy to check that in fact any number that "works" is a multiple of the smallest one.
Now, as to the "short-cut": it relies on two facts:
- We know what the value is for prime powers. And
- The Carmichael function satisfies the following: if $m$ and $n$ are relatively prime, then $C(mn) = \mathrm{lcm}(C(m),C(n))$.
The latter assertion follows from the Chinese Remainder Theorem: the positive integers smaller than $mn$ that are coprime to $mn$ are in one-to-one correspondence to pairs of integers $(a,b)$ with $0\lt a\lt m$, $0\lt b\lt n$, and $\gcd(a,m)=\gcd(b,n)=1$ (namely, given $x$, $0\lt x\lt mn$ coprime to $mn$, set $a=x\bmod m$ and $b=x\bmod n$ (the Chinese Remainder Theorem guarantees that this is a bijection). And $x^r\equiv 1\pmod{mn}$ if and only if $a^r\equiv 1\pmod{m}$ and $b^r\equiv 1\pmod{n}$. Thus, any number that is a multiple of both $C(m)$ and $C(n)$ will "work" for $mn$, and any number that "works" for $mn$ must be a multiple of $C(m)$ and of $C(n)$. Hence, the set of integers that "work" are the common multiples of $C(m)$ and $C(n)$, and so the smallest integer that works is the least common multiple.
As to the value in the prime factors, for odd primes, this is just Euler's Theorem; it takes a bit of work, but one can show that if $p$ is an odd prime, then $C(p^r) = (p-1)p^{r-1}$.
For $p=2$, we have that $C(2)=1$, $C(4) = 2$, and $C(2^{r}) = 2^{r-2}$ if $r\geq 3$.
These formulas give you a way to compute $C$ for any integer that you can factor into primes.