Euler’s theorem

E300757

result in modular arithmetic theorem in number theory

Euler’s theorem is a fundamental result in number theory stating that for any integer a coprime to n, a raised to the power of φ(n) is congruent to 1 modulo n.

Try in SPARQL Jump to: Surface forms Statements Referenced by

All labels observed (2)

Label	Occurrences
Euler's theorem	2
Euler’s theorem canonical	1

Statements (47)

Predicate	Object
instanceOf	result in modular arithmetic ⓘ theorem in number theory ⓘ
appearsIn	introductory number theory textbooks ⓘ
appliesTo	any integer a with gcd(a,n)=1 ⓘ any positive integer n ≥ 1 ⓘ
assumption	gcd(a,n)=1 ⓘ
category	elementary number theory ⓘ multiplicative number theory ⓘ
conclusion	a^{φ(n)} ≡ 1 (mod n) ⓘ
contrastsWith	Wilson's theorem ⓘ surface form: Wilson’s theorem
dependsOn	finiteness of (Z/nZ)^× ⓘ group exponent properties ⓘ
domain	integers coprime to n ⓘ
equivalentForm	For a in (Z/nZ)^×, a^{\| (Z/nZ)^× \|} = 1 ⓘ
field	modular arithmetic ⓘ number theory ⓘ
generalizes	Fermat's little theorem ⓘ surface form: Fermat’s little theorem
hasComponent	Euler’s totient function φ(n) ⓘ condition of coprimality ⓘ modulo n congruence relation ⓘ
holdsIn	multiplicative group of units modulo n ⓘ
implies	a^{k·φ(n)} ≡ 1 (mod n) for any integer k ⓘ a^{φ(n)+m} ≡ a^{m} (mod n) when gcd(a,n)=1 ⓘ
isStrongerThan	Fermat’s little theorem for composite moduli ⓘ
language	mathematical notation ⓘ
namedAfter	Leonhard Euler ⓘ
proofMethod	combinatorial counting argument ⓘ group-theoretic argument ⓘ
relatedTo	Chinese remainder theorem ⓘ group theory ⓘ multiplicative group modulo n ⓘ
requires	φ(n) to be well-defined ⓘ
specialCase	Fermat’s little theorem when n is prime ⓘ
statedAs	If gcd(a,n)=1 then a^{φ(n)} ≡ 1 (mod n) ⓘ
usedFor	computing modular inverses ⓘ reducing large exponents modulo n ⓘ simplifying congruences ⓘ
usedIn	RSA ⓘ surface form: RSA cryptosystem modular exponentiation algorithms ⓘ primality testing methods ⓘ public-key cryptography ⓘ
usesConcept	Euler’s totient function φ(n) ⓘ surface form: Euler’s totient function greatest common divisor ⓘ modular congruence ⓘ
validFor	composite moduli ⓘ prime moduli ⓘ
yearIntroducedApprox	18th century ⓘ

Referenced by (3)

Full triples — surface form annotated when it differs from this entity's canonical label.

Euler’s totient function φ(n) → roleIn → Euler’s theorem ⓘ

Fermat's little theorem → relatedTo → Euler’s theorem ⓘ

this entity surface form: Euler's theorem

Fermat's little theorem → generalizedBy → Euler’s theorem ⓘ

this entity surface form: Euler's theorem