MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 Smarandache's paper

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

share|cite|improve this question

closed as off topic by Dan Petersen, Felipe Voloch, Mark Sapir, Bill Johnson, Andy Putman Jan 16 '12 at 5:01

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

Yes. Joe Roberts book on Elementary Number Theory has some. There is also Carmichael's lambda function. You may find some more with a well crafted search term and an Internet search. Gerhard "Ask Me About System Design" Paseman, 2012.01.13 – Gerhard Paseman Jan 14 '12 at 6:46
As to 2, the number $\frac{1}{n}\sum_{d|n}\mu(d)a^{\frac{n}{d}}$ is certainly an integer, as it is the number of aperiodic necklaces with $n$ beads of $a$ colors, – Pietro Majer Jan 14 '12 at 7:59
I've never seen a list of mathematicians begin with Fermat and Euler and end with Smarandache, and I hope I never have to see such a thing again. – Andy Putman Jan 16 '12 at 5:05
If you intend to cast a vote to delete, please note it was undeleted already once and moderators 'cleared' votes to delete. If you really want this deleted please start a meta thread. Otherwise this just wastes everybodies time. – quid Jun 6 '13 at 14:04
up vote 14 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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