proof of Euler-Fermat theorem using Lagrange’s theorem


Given a,nZ, aϕ(n)1(modn) when 𝑔𝑐𝑑(a,n)=1, where ϕ is the Euler totient function.


We will make use of Lagrange’s Theorem: Let G be a finite groupMathworldPlanetmath and let H be a subgroupMathworldPlanetmathPlanetmath of G. Then the order of H divides the order of G.

Let G=(/n)× and let H be the multiplicative subgroup of G generated by a (so H={1,a,a2,}). The fact that gcd(a,n)=1 ensures that aG. Notice that the order of H, h=|H| is also the order of a, i.e. the smallest natural numberMathworldPlanetmath n>1 such that an is the identityPlanetmathPlanetmathPlanetmath in G, i.e. ah1modn. Also, recall that the order of G=(/n)× is ϕ(n), where ϕ is the Euler ϕ function.

By Lagrange’s theorem h|G|=ϕ(n), so ϕ(n)=hm for some m. Thus:


as claimed. ∎

Title proof of Euler-Fermat theorem using Lagrange’s theorem
Canonical name ProofOfEulerFermatTheoremUsingLagrangesTheorem
Date of creation 2013-03-22 14:24:03
Last modified on 2013-03-22 14:24:03
Owner alozano (2414)
Last modified by alozano (2414)
Numerical id 4
Author alozano (2414)
Entry type Proof
Classification msc 11-00
Related topic LagrangesTheorem
Related topic FermatsLittleTheorem
Related topic FermatsTheoremProof