Intereting Posts

Laws of Exponents for Cosets – Fraleigh p. 142 14.22
Prove Borel Measurable Set A with the following property has measure 0.
use of $\sum $ for uncountable indexing set
Is a measure for a sigma algebra determined by its values for a generator of the sigma algebra?
Book/tutorial recommendations: acquiring math-oriented reading proficiency in German
Olympiad Inequality $\sum\limits_{cyc} \frac{x^4}{8x^3+5y^3} \geqslant \frac{x+y+z}{13}$
Linear isoparametrics with dual finite elements
Can every element in the stalk be represented by a section in the top space?
Value of $\sum_{k=1}^{\infty}\frac{1}{k^2+a^2}$
What makes Tarski Grothendieck set theory non-empty?
How to prove cardinality equality ($\mathfrak c^\mathfrak c=2^\mathfrak c$)
Characterize the groups $G$ for which the map $\iota: G \to G$, sending $x \mapsto x^{-1}$ for all $x \in G$, is an automorphism of $G$
Prove that $A$ is diagonalizable iff $\mbox{tr} A\neq 0$
True or False. Convergent subsequence
Evaluating sums using residues $(-1)^n/n^2$

Euler’s Theorem

$$a^{\phi(n)}\equiv 1\pmod n,$$

which is valid only iff $a$ and $n$ are coprime, can be “generalized” a bit to

$$a^{\phi(n)+1}\equiv a\pmod n, (*)$$

where some zero-divisors of $n$ are also admissible for $a$, e.g.

$$2^4\equiv 2\pmod{10},$$

while what I would like to call zero-roots^{$\dagger$} of $n$ fail:

$$6^4\equiv 0\pmod{12}$$

But apart from these, does the generalization $(*)$ hold for all non-zero-roots of $n$?

$\dagger$ $a$ is a zero-root of $n$ $\Leftrightarrow$ $\exists k:a^k\equiv0\pmod n$ – this is the case iff all prime factors of $a$ and $n$ are the same

- 2011 AIME Problem 12, probability round table
- The last 2 digits of $7^{7^{7^7}}$
- Find general solution for the equation $1 + 2 + \cdots + (n − 1) = (n + 1) + (n + 2) + \cdots + (n + r) $
- Help in understanding the proof of Mersenne Prime
- No integer solutions for $x^5 - 3y^5 = 2008$
- congruence issue

- A trigonometric identity for special angles
- How can you prove that the square root of two is irrational?
- Proof of the formula for Euler's totient function
- If $n$ is an even perfect number $ n> 6$ show that the sum of its digits is $\equiv 1 (\bmod 9)$
- Is 0.9999… equal to -1?
- A function can provide the complete set of Euler primes via a Mill's-like constant. Is it useful or just a curiosity?
- Is my intuition of “If $p \mid ab$ then $p \mid a$ or $p \mid b$” correct?
- Show that a Sophie Germain prime $p$ is of the form $6k - 1$ for $p > 3$
- If a number can be expressed as a product of n unique primes…
- Odd binomial sum equality has only trivial solution?

The congruence

$$a^{\varphi(n)+1} \equiv a \pmod{n},$$

or, for that matter,

$$a^{\lambda(n)+1} \equiv a \pmod{n},$$

holds if and only if for all primes $p$ dividing $n$ we have $p \nmid a$ or $v_p(a) \geqslant v_p(n)$ (where $v_p(k)$ is the multiplicity of $p$ in the prime factorisation of $k$, so $p^{v_p(k)} \mid k$, but $p^{v_p(k)+1} \nmid k$).

To see that, consider a prime $p$ dividing $n$, and let $k = v_p(n)$. Then $\varphi(p^k) = (p-1)p^{k-1}$ divides $\lambda(n)$ and a fortiori $\varphi(n)$. Now let $a$ arbitrary. If $p \nmid a$, then $a^{\lambda(n)} \equiv a^{\varphi(n)} \equiv 1 \pmod{p^k}$, and $a^{\lambda(n)+1} \equiv a^{\varphi(n)+1} \equiv a \pmod{p^k}$. And if $p\mid a$, then

$$v_p(a^{\lambda(n)}) \stackrel{\varphi(p^k)\mid\lambda(n)}\geqslant v_p(a^{\varphi(p^k)}) \stackrel{p\mid a}\geqslant \varphi(p^k) = p^{k-1}(p-1) \geqslant p^{k-1} \geqslant k,$$

so $a^{\lambda(n)} \equiv 0 \pmod{p^k}$, and a fortiori $a^{\lambda(n)+1} \equiv 0 \pmod{p^k}$ and $a^{\varphi(n)+1}\equiv 0 \pmod{p^k}$. So if $p \mid a$, we have $a^{\lambda(n)+1} \equiv a \pmod{p^k} \iff a \equiv 0 \pmod{p^k}$ (and ditto for $\varphi(n)$).

Since $a^e \equiv a \pmod{n}$ if and only if $a^e \equiv a \pmod{p^{v_p(n)}}$ for all primes dividing $n$ (that last condition is not necessary, if $p \nmid n$, we have $a^e \equiv a \pmod{p^0}$ regardless), the result follows.

It holds at least for squarefree $n$ (which explains your mod 12 exception). This is already valid for the Carmichael function $\lambda(n)$, see http://en.wikipedia.org/wiki/Carmichael_function#Exponential_cycle_length

Another way:

$$\begin{align}

a^{\phi(n)+1} &\equiv a \pmod n \quad(*)

\\\Leftrightarrow a^{\phi(n)} &\equiv 1 \pmod{n/\gcd(n,a)}

\end{align}$$

If $a$ and $n$ are coprime (i.e. $\gcd(n,a)=1$), this is simply Euler’s Theorem and therefore true. Otherwise, since

$$ \phi(a\cdot b) = \phi(a)\phi(b)\frac{\gcd(a,b)}{\phi(\gcd(a,b))},$$

let $g:=\gcd(n,a)$ and $m:=n/g$ to obtain

$$\begin{align}

\phi(n) &= \phi(m\cdot g)

\\ &= \phi(m)\cdot\underbrace{\frac{\phi(g)\gcd(m,g)}{\phi(\gcd(m,g))}}_{=:k}

\end{align}$$

and therefore

$$(*)\Leftrightarrow \left(a^k\right)^{\phi(m)} \equiv 1\pmod m$$

which is again Euler’s theorem that holds iff $a^k$ and $m$ are coprime where $k=\phi(n)/\phi(m)$ and $m=n/\gcd(n,a)$.

I’ll try to correlate this to Daniel Fischer’s requirements later on…

- A non-noetherian ring with $\text{Spec}(R)$ noetherian
- In how many ways can $2n$ players be paired?
- Does the Schur complement preserve the partial order
- boundary of the boundary of a set is empty
- A Golden Ratio Symphony! Why so many golden ratios in a relatively simple golden ratio construction with square and circle?
- On the closed form for $\sum_{m=0}^\infty \prod_{n=1}^m\frac{n}{5n-1}$
- Using Modularity Theorem and Ribet's Theorem to disprove existence of rational solutions
- Maximize $\gamma$ such that $A+\gamma B\succeq 0$
- Need a result of Euler that is simple enough for a child to understand
- Distance is (uniformly) continuous
- Is an ultrafilter free if and only if it contains the cofinite filter?
- If $(|G|, |H|) > 1$, does it follow that $\operatorname{Aut}(G \times H) \neq \operatorname{Aut}(G) \times \operatorname{Aut}(H)$?
- Can Euler's identity be extended to quaternions?
- Showing that $\operatorname {Br}(\Bbb F_q)=0$
- If $p$ is a positive multivariate polynomial, does $1/p$ have polynomial growth?