Intereting Posts

Showing that $1/x$ is NOT Lebesgue Integrable on $(0,1]$
Riemann Hypothesis and the prime counting function
Homomorphisms of graded modules
Stuck with proof for $\forall A\forall B(\mathcal{P}(A)\cup\mathcal{P}(B)=\mathcal{P}(A\cup B)\rightarrow A\subseteq B \vee B\subseteq A)$
Intuition about infinite sums
Area of convex n-gon using triangles
Swapping limits: $\lim_{h\to 0}\lim_{n\to \infty}\frac {(1+1/n)^{hn}-1}{h}=\lim_{n\to\infty}\lim_{h\to 0}\frac {(1+1/n)^{hn}-1}{h}$
How to construct the point of intersection of a line and a parabola whose focus and directrix are known?
Pole set of rational function on $V(WZ-XY)$
Ring of integers of a cubic number field
Does the everywhere differentiability of $f$ imply it is absolutely continuous on a compact interval?
Approaching a contour integral with singularities on each axis
Existence of a normal subgroup with $|\operatorname{Aut}{(H)}|>|\operatorname{Aut}{(G)}|$
probability question related to pattern in coin tossing
Vieta Jumping: Related to IMO problem 6, 1988: If $ab + 1$ divides $a^2 + b^2$ then $ab + 1$ cannot be a perfect square.

I am having some trouble with this proof and I need some help heading down the right direction:

Suppose $n = p_1p_2 \cdots p_k$ where $p_i$ are distinct primes and that $p_i – 1 \mid n – 1$. Show that $n$ is a Carmichael number, that is, that $a^{n – 1} \equiv 1 \pmod n$ for all $a$ with $\gcd(a, n) = 1$.

Thank you for your help.

- An analogue of Hensel's lifting for Fibonacci numbers
- Inverse modulo question?
- What's the proof that the Euler totient function is multiplicative?
- $\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}?$
- Show that if $(a,n)=d>1$ and $k$ is any positive integer, then $a^k\not\equiv 1\pmod{n}.$
- How to find positive integer solution of bilinear transformation?

- Primes dividing $11, 111, 1111, …$
- $p$-Splittable Integers
- $n^5-n$ is divisible by $10$?
- Derivation of Pythagorean Triple General Solution Starting Point:
- Counting $x$ where $an < x \le (an+n)$ and lpf($x$) $ \ge \frac{n}{4}$ and $1 \le a \le n$
- $ \exists a, b \in \mathbb{Z} $ such that $ a^2 + b^2 = 5^k $
- Does $a^n \mid b^n$ imply $a\mid b$?
- $\gcd(a,\operatorname{lcm}(b,c))=\operatorname{lcm}(\gcd(a,b),\gcd(a,c))$
- Proving the so-called “Well Ordering Principle”
- What is the difference between Hensel lifting and the Newton-Raphson method?

Actually much stronger is true. We have that

For $n > 2$, $n$ is Carmichael if and only if $n = \prod_{i=1}^k p_i$, where the $p_i$ are distinct primes with $k \geq 2$ and $p_i – 1 \mid n – 1$ for every $i$.

The proof is as follows

Assume $n = \prod_{i=1}^k p_i$, where the $p_i$ are distinct primes with $k \geq 2$ and $p_i – 1 \mid n – 1$ for every $i$. For $b \in \Bbb{Z}$, we have that, if $p_i \mid b$,then $b^n \equiv 0 \equiv b \pmod{p_i}$ and if $p_i \nmid b$,then $b^{n – 1} \equiv b^{(p_1 -1)\ell} \equiv 1 \pmod{p_i}$. So $b^{n} \equiv b \pmod{p_i}$. Therefore by the Chinese Remainder Theorem,

$$

b^n \equiv b \pmod{n}

$$

and hence $n$ is Carmichael.Conversely suppose that $n$ is Carmichael. First we will prove that $n$ is squarefree. Assume by contradiction that it is not squarefree. Then there exists some integer $v$ such that $v^2 \mid n$. Now we have that $v^n \equiv v \pmod{n}$ since $n$ is Carmichael. So this implies that $n \mid v^n – v$. Since $v^2 \mid v^n$ (since $n$ is Carmichael, it is composite and hence $n > 2$) and $v^2 \mid n$ we have that $v^2 \mid v$ which is impossible. So $n$ is squarefree. Since $n$ is squarefree, $n = p_1 \cdots p_k$ for distinct primes $p_i$.

Since $n$ is Carmichael, we have that

$$

b^n \equiv b \pmod{n}

$$

for all integers $b$ such that $gcd(b, n) = 1$. Therefore $b^{n-1} \equiv 1 \pmod{n}$. So we have that $ord_n(b)$ divides $n – 1$. In particular we have that the universal exponent of $U_n$, which we denote $\kappa_n$, where $U_n$ is the unit group of $\Bbb{Z}/n\Bbb{Z}$, which consists of all the elements in $\Bbb{Z}/n\Bbb{Z}$ that are coprime to $n$, divides $n-1$. Since

$$

\kappa_n = lcm (\kappa_{p_i}) = lcm(p_i – 1)

$$

we have that $p_i – 1 \mid n-1$ for all $i$. This completes our proof.

- Limit of $\frac{\sin(x+y)}{x+y}$ as $(x,y) \to (0,0)$
- Prove $\int_{0}^{x}f+\int_{0}^{f(x)}f^{-1}=xf(x)\qquad\text{for all $x\geq0$}$
- Please explain the logic behind $d(xy) = y(dx) + x(dy)$
- Classification Theorem for Non-Compact 2-Manifolds? 2-Manifolds With Boundary?
- If we accept a false statement, can we prove anything?
- Probability Bertsekas Question
- If $9^{x+1} + (t^2 – 4t – 2)3^x + 1 > 0$, then what values can $t$ take?
- Total number paths between two nodes in a complete graph
- At a party $n$ people toss their hats into a pile in a closet.$\dots$
- Proof that if $\gcd(a,b) = 1$ and $a\mid n$ and $b\mid n$, $ab \mid n$
- an example of an interesting connected topological space
- What is the meaning of $DX_p$ for $X$ a vector field on a manifold?
- Necessary and sufficient conditions for when spectral radius equals the largest singular value.
- Why isn't the gamma function defined so that $\Gamma(n) = n! $?
- Why are two permutations conjugate iff they have the same cycle structure?