## You are here

Homeproof of Euler-Fermat theorem

## Primary tabs

# proof of Euler-Fermat theorem

Let $a_{1},a_{2},\ldots,a_{{\phi(n)}}$ be all positive integers less than $n$ which are coprime to $n$. Since $\text{gcd}(a,n)=1$, then the set $aa_{1},aa_{2},\ldots,aa_{{\phi(n)}}$ are each congruent to one of the integers $a_{1},a_{2},\ldots,a_{{\phi(n)}}$ in some order. Taking the product of these congruences, we get

$(aa_{1})(aa_{2})\cdots(aa_{{\phi(n)}})\equiv a_{1}a_{2}\cdots a_{{\phi(n)}}\;% \;(\mathop{{\rm mod}}n)$ |

hence

$a^{{\phi(n)}}(a_{1}a_{2}\cdots a_{{\phi(n)}})\equiv a_{1}a_{2}\cdots a_{{\phi(% n)}}\;\;(\mathop{{\rm mod}}n).$ |

Keywords:

number theory

Major Section:

Reference

Type of Math Object:

Proof

Parent:

## Mathematics Subject Classification

11A07*no label found*11A25

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Corrections

Kind of a typo by mathwizard ✓

## Comments

## Another Proof.

We can prove the theorem as a trivial application of Lagrange's theorem

applied to the group of units in integers modulo n.

## .

1. function is phi, not theta

2. please mention that

if gcd(a,n)=1, gcd(a_i,n)=1,

then gcd(a*a_i,n)=1