Any more generalization of Fermat's Little Theorem? - MathOverflow [closed]

Any more generalization of Fermat's Little Theorem?

2012-01-14T06:24:23Z

Fermat's Little Theorem: If $p$ is a prime and $\gcd(a,p)=1$ then $a^{p-1} \equiv1\pmod p$.

Over the years, Fermat's Little Theorem have been generalized in several ways. I am aware of four different generalizations as given below.

1. Euler: If $\gcd(a,n)=1$ then $a^{\phi(n)} \equiv1 \pmod n$.

2. Ramachandra: $\sum_{d|n}\mu(d)a^{n/d} \equiv 0\pmod n$. (Fermat's Little Theorem follows when $n=p$ is a prime and has only two divisors 1 and $p$.

3. Let $d$ be a divisor of $\phi(n)$. There are exactly $d$ distinct positive integers $r_k, (k=1,2, \ldots d)$ such if $\gcd(x,n)=1$ then $x^{\phi(n)/d} \equiv r_k \pmod n$ for some $(k=1,2, \ldots d)$ (Euler's generalization itself is a special case of this result when $d=1$.)

4. Florentin Smarandache: $a^{\phi(n_s)+s} \equiv a^s \pmod n$ where $s$ and $n_s$ are defined in Samarandache's paper

I would like to know if there is any other generalization of Fermat's Little Theorem.

Answer by Chandan Singh Dalawat for Any more generalization of Fermat's Little Theorem?

2012-01-14T07:02:35Z

Fermat's little theorem is a consequence of the fact that the group $(\mathbf{Z}/p\mathbf{Z})^\times$ is cyclic of order $p-1$. Euler's theorem is a consequence of the fact that the (commutative) group $(\mathbf{Z}/n\mathbf{Z})^\times$ has order $\varphi(n)$.

What happens when we replace $\mathbf{Z}$ by the ring of integers $\mathfrak{o}$ in some number field ? If we take a prime ideal $\mathfrak{p}$ of $\mathfrak{o}$, then the quotient $\mathfrak{o}/\mathfrak{p}$ is a finite field; if it has $q$ elements, then $$ x^{q-1}\equiv 1\pmod{\mathfrak{p}} $$ for every $x\in\mathfrak{o}$ not in $\mathfrak{p}$. There is an obvious generalisation to the case of an arbitrary ideal $\mathfrak{a}\subset\mathfrak{o}$ and $x\in\mathfrak{o}$ prime to $\mathfrak{a}$ in the sense that $x\mathfrak{o}+\mathfrak{a}=\mathfrak{o}$.

Answer by Franz Lemmermeyer for Any more generalization of Fermat's Little Theorem?

2012-01-14T13:02:14Z

Consider a Pell conic ${\mathcal C}: X^2 - mY^2 = 1$ with the point $N = (1,0)$. Given a field $K$ with $m \ne 0$ define a group law on the set ${\mathcal C}(K)$ of points on ${\mathcal C}$ with coordinates from $K$ as follows: the sum $P + Q$ of two points is the second point of intersection of ${\mathcal C}$ and the line parallel to $PQ$ through $N$. If $P = Q$, replace the line $PQ$ by the tangent to ${\mathcal C}$ at $P$. The resulting formulas $$ (x_1,y_1) + (x_2,y_2) = (x_3,y_3), \quad x_3 = x_1x_2 + my_1y_2, \quad y_3 = x_1y_2 + x_2y_1 $$ define a group law on ${\mathcal C}(R)$ over arbitrary domains $R$ (e.g. $R = {\mathbb Z}$ or $R = {\mathbb Z}/n{\mathbb Z}$) with neutral element $N$ and inverse $-(x,y) = (x,-y)$.

The group ${\mathcal C}({\mathbb F}_p)$ is cyclic of order $k = p - (\frac{m}{p})$ for primes $p$ not dividing $m$. Lagrange's Theorem, as in Chandan's answer, implies that $kP = N$ for all $P \in {\mathcal C}({\mathbb F}_p)$. If $(m/p) = +1$, this is Fermat's Theorem. Euler's theorem follows by working modulo composite numbers.

The obvious advantage of this formulation is that all primality tests and factorization algorithms based on the factorizations of $p-1$ and $p+1$ can be treated simultaneously. All this can be generalized even further to tori.

Answer by Qiaochu Yuan for Any more generalization of Fermat's Little Theorem?

2012-01-14T15:27:16Z

Let $A$ be a square integer matrix. Then $$\sum_{d | n} \mu(d) \text{tr}(A^{n/d}) \equiv 0 \bmod n.$$ After assuming WLOG that $A$ has non-negative entries, the clearest proof I know of this result proceeds by relating the above expression to aperiodic walks on a graph with adjacency matrix $A$; see these two blog posts.