Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I understand that the Carmichael Function (I'm going to call C()) is essentially the smallest positive integer m, where $a^m$ is congruent $1 \pmod n$ for all co-primes less than n.

6 makes sense to me. The only co-prime is 5 and $5^2 = 25\equiv 1 \pmod 6$. So $C(6) = 2$.

I also know that the answer to $C(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.

share|improve this question
    
Carmichael reduces to Euler-Fermat for odd prime powers. So attempting to understand it without Euler-Fermat is akin to attempting to learn how to run before you can walk. What are you having difficulties understanding? –  Bill Dubuque Jul 6 '12 at 21:23
    
How do you explain that such an $m$ even exists? If you're that far, you may as well introduce Euler's theorem, I think. –  Cocopuffs Jul 6 '12 at 21:23
    
Don't forget that $1$ is coprime to $6$; true, only $5$ "matters" because $1^1\equiv 1\pmod{6}$, but still, saying things like "the only co-prime [to 6] is 5" is saying incorrect things. –  Arturo Magidin Jul 6 '12 at 21:27
    
Fermat and Euler can be explained to a bright 14-year-old who is interested ... . I had taught myself by that age from the books on my father's bookshelf. I would not waste beautiful mathematics on a 14-year-old who is not ready to learn and enjoy it ... so how are you going to motivate them? –  Mark Bennet Jul 6 '12 at 21:30
2  
The fact that $m$ exists follows simply because there are only finitely many positive integers coprime to $m$; each one must have a power that is equal to $1$ modulo $m$ (successively raising $a$ to different powers must yield a repeat, since there are only finitely many possible answers, all coprime to $n$; if $a^k = a^{\ell}$ with $k\leq \ell$, then $a^{\ell-k}\equiv 1\pmod{n}$. And if $k$ "works" for $a$, then so does every multiple of $a$. So you just need to find the least common multiple of a finite set of positive integers... which always exists. –  Arturo Magidin Jul 6 '12 at 21:30

1 Answer 1

up vote 5 down vote accepted

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 $bd$), 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:

  1. We know what the value is for prime powers. And
  2. 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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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