Intereting Posts

What is the binomial sum $\sum_{n=1}^\infty \frac{1}{n^5\,\binom {2n}n}$ in terms of zeta functions?
Understanding the solution to $\lim_{n\to\infty}\frac{a^n}{n!}, a>1$
Unique intermediate subgroup and double coset relation I
Proving $\left(A-1+\frac1B\right)\left(B-1+\frac1C\right)\left(C-1+\frac1A\right)\leq1$
Solutions to exp(x) + x = 2
Prime factors + number of Divisors
Can the zero vector be an eigenvector for a matrix?
A non-noetherian ring with $\text{Spec}(R)$ noetherian
when is $\frac{1}{n}\binom{n}{r}$ an integer
What's the geometrical interpretation of the magnitude of gradient generally?
Poincare-Bendixson Theorem
equation involving the integral of the modular function of a topological group
A set is a finite chain if every subset has a top and bottom element
Formula for $\zeta(3)$ -verification
Linear independence of fractional powers

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 $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 $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.

- Proof of linear independence of $e^{at}$
- Deriving even odd function expressions
- $\lfloor \sqrt n+\sqrt {n+1}+\sqrt{n+2}+\sqrt{n+3}+\sqrt{n+4}\rfloor=\lfloor\sqrt {25n+49}\rfloor$ is true?
- Sequence of continuous functions converges uniformly. Does it imply the limit function is continuous?
- Overview of basic results about images and preimages
- Prove that there is C such that $f(c)=0$

- Example of a function $f$ which is nowhere continuous but $|f|$ should be continuous at all points
- Describing a Wave
- Specific Modular Arithmetic Question with Exponentiation
- How is the Integral of $\int_a^bf(x)~dx=\int_a^bf(a+b-x)~dx$
- Analytic method for determining if a function is one-to-one
- How do I prove that there infinitely many rows of Pascal's triangle with only odd numbers?
- How to compute $2^{\text{some huge power}}$
- Prove or disprove that $\exists a,b,c\in\mathbb{Z}_+\ \forall n\in\mathbb{Z}_+\ \exists k\in\mathbb{Z}_+\colon\ a^k+b^k+c^k = 0(\mathrm{mod}\ 2^n)$
- Differentiate $\sin \sqrt{x^2+1} $with respect to $x$?
- what is the remainder when $1!+2!+3!+4!+\cdots+45!$ is divided by 47?

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 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.

- Proving $a\mid b^2,\,b^2\mid a^3,\,a^3\mid b^4,\ldots\implies a=b$ – why is my approach incorrect
- Show that for any positive integer $n$ there is $x \in $ for which $f(x) = f(x+\frac{1}{n})$
- improper integral $\int_{0}^{\infty } \frac{5x}{e^{x}-e^{-x}}$
- What do higher cohomologies mean concretely (in various cohomology theories)?
- Countable Chain Condition for separable spaces?
- Find the sign of $\int_{0}^{2 \pi}\frac{\sin x}{x} dx$
- If $\lim f(x)$ exists and $\lim g(x)$ do not, when $x$ approaches $a$ , why $\lim$ does not exist?
- How much area in a unit square is not covered by $k$ disks of area $1/k$ centered at random points within the square?
- Cesaro summable implies Abel summable
- Efficient and Accurate Numerical Implementation of the Inverse Rodrigues Rotation Formula (Rotation Matrix -> Axis-Angle)
- Proving that $\sqrt{2}+\sqrt{3}$ is irrational
- The mode of the Poisson Distribution
- Visual Ways to Remember Cross products of Unit vectors? Cross-product in $\mathbb F^3$?
- Is this the general solution of finding the two original squares that add up to a given integer N?
- How to prove there are exactly eight convex deltahedra?