Any more generalization of Fermat's Little Theorem? - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-19T17:48:20Z http://mathoverflow.net/feeds/question/85635 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85635/any-more-generalization-of-fermats-little-theorem Any more generalization of Fermat's Little Theorem? Xaus 2012-01-14T06:24:23Z 2012-01-14T15:27:16Z <p><strong>Fermat's Little Theorem</strong>: If $p$ is a prime and $\gcd(a,p)=1$ then $a^{p-1} \equiv1\pmod p$.</p> <p>Over the years, Fermat's Little Theorem have been generalized in several ways. I am aware of four different generalizations as given below.</p> <p><strong>1. Euler</strong>: If $\gcd(a,n)=1$ then $a^{\phi(n)} \equiv1 \pmod n$.</p> <p><strong>2. Ramachandra</strong>: $\sum_{d|n}\mu(d)a^{n/d} \equiv 0\pmod n$. (<em>Fermat's Little Theorem follows when $n=p$ is a prime and has only two divisors 1 and $p$</em>. </p> <p><strong>3</strong>. 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)$ (<em>Euler's generalization itself is a special case of this result when $d=1$</em>.)</p> <p><strong>4. Florentin Smarandache</strong>: $a^{\phi(n_s)+s} \equiv a^s \pmod n$ where $s$ and $n_s$ are defined in <a href="http://arxiv.org/ftp/math/papers/0610/0610607.pdf" rel="nofollow">Samarandache's paper</a></p> <p>I would like to know if there is any other generalization of Fermat's Little Theorem. </p> http://mathoverflow.net/questions/85635/any-more-generalization-of-fermats-little-theorem/85637#85637 Answer by Chandan Singh Dalawat for Any more generalization of Fermat's Little Theorem? Chandan Singh Dalawat 2012-01-14T07:02:35Z 2012-01-14T10:40:41Z <p>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)$. </p> <p>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}$. </p> http://mathoverflow.net/questions/85635/any-more-generalization-of-fermats-little-theorem/85660#85660 Answer by Franz Lemmermeyer for Any more generalization of Fermat's Little Theorem? Franz Lemmermeyer 2012-01-14T13:02:14Z 2012-01-14T13:02:14Z <p>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)$. </p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/85635/any-more-generalization-of-fermats-little-theorem/85670#85670 Answer by Qiaochu Yuan for Any more generalization of Fermat's Little Theorem? Qiaochu Yuan 2012-01-14T15:27:16Z 2012-01-14T15:27:16Z <p>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 <a href="http://qchu.wordpress.com/2009/08/23/newtons-sums-necklace-congruences-and-zeta-functions/" rel="nofollow">these</a> <a href="http://qchu.wordpress.com/2009/11/04/newtons-sums-necklace-congruences-and-zeta-functions-ii/" rel="nofollow">two</a> blog posts. </p>