# proof of Euler-Fermat theorem

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

$$(a{a}_{1})(a{a}_{2})\mathrm{\cdots}(a{a}_{\varphi (n)})\equiv {a}_{1}{a}_{2}\mathrm{\cdots}{a}_{\varphi (n)}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$$ |

hence

$${a}^{\varphi (n)}({a}_{1}{a}_{2}\mathrm{\cdots}{a}_{\varphi (n)})\equiv {a}_{1}{a}_{2}\mathrm{\cdots}{a}_{\varphi (n)}\phantom{\rule{veryverythickmathspace}{0ex}}(modn).$$ |

Since $\text{gcd}({a}_{1}{a}_{2}\mathrm{\cdots}{a}_{\varphi (n)},n)=1$, we can divide both sides by ${a}_{1}{a}_{2}\mathrm{\cdots}{a}_{\varphi (n)}$, and the desired result follows.

Title | proof of Euler-Fermat theorem |
---|---|

Canonical name | ProofOfEulerFermatTheorem |

Date of creation | 2013-03-22 11:47:57 |

Last modified on | 2013-03-22 11:47:57 |

Owner | KimJ (5) |

Last modified by | KimJ (5) |

Numerical id | 10 |

Author | KimJ (5) |

Entry type | Proof |

Classification | msc 11A07 |

Classification | msc 11A25 |