Chinese remainder theorem

E530312

result in number theory theorem

The Chinese remainder theorem is a fundamental result in number theory that provides conditions and a method for solving systems of simultaneous congruences with pairwise coprime moduli.

Try in SPARQL Jump to: Surface forms Statements Referenced by

All labels observed (1)

Label	Occurrences
Chinese remainder theorem canonical	3

Statements (49)

Predicate	Object
instanceOf	result in number theory ⓘ theorem ⓘ
appearsIn	Sunzi Suanjing NERFINISHED ⓘ
appliesTo	modular arithmetic ⓘ systems of congruences with pairwise coprime moduli ⓘ
associatedWith	Sunzi NERFINISHED ⓘ
category	arithmetic theorems ⓘ theorems in abstract algebra ⓘ
describes	solutions of systems of simultaneous congruences ⓘ
ensures	every residue system modulo product corresponds to a tuple of residues modulo each modulus ⓘ
field	number theory ⓘ
formalizes	reconstruction of integers from residue classes ⓘ
hasAlternativeName	CRT NERFINISHED ⓘ
hasFormulation	integer arithmetic formulation ⓘ ring-theoretic formulation ⓘ
hasGeneralization	Chinese remainder theorem for ideals NERFINISHED ⓘ Chinese remainder theorem for rings NERFINISHED ⓘ Chinese remainder theorem in commutative algebra NERFINISHED ⓘ
hasHistoricalOrigin	ancient Chinese mathematics ⓘ
hasProofTechnique	constructive proof using modular inverses ⓘ proof using Bezout coefficients ⓘ proof using ring isomorphisms ⓘ
implies	isomorphism Z/(n1⋯nk)Z ≅ Z/n1Z × ⋯ × Z/nkZ for pairwise coprime ni ⓘ
involves	congruence relations ⓘ moduli ⓘ pairwise coprime integers ⓘ
provides	existence conditions for simultaneous solutions ⓘ uniqueness conditions for simultaneous solutions modulo the product of the moduli ⓘ
relatedTo	Bezout's identity NERFINISHED ⓘ Euclidean algorithm NERFINISHED ⓘ direct product of rings ⓘ modular inverses ⓘ ring isomorphisms ⓘ
requiresCondition	pairwise coprimality of moduli ⓘ
states	if moduli are pairwise coprime then a simultaneous solution exists ⓘ if moduli are pairwise coprime then the solution is unique modulo the product of the moduli ⓘ
subfield	elementary number theory ⓘ
usedFor	calendar calculations ⓘ clock arithmetic problems ⓘ solving congruence-based puzzles ⓘ speeding up modular exponentiation ⓘ
usedIn	RSA algorithm NERFINISHED ⓘ algorithmic Chinese remainder representation of integers ⓘ coding theory ⓘ computational number theory ⓘ computer algebra systems ⓘ cryptography ⓘ integer reconstruction from residues ⓘ parallel computation of modular operations ⓘ

Referenced by (3)

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

Fermat's little theorem → relatedTo → Chinese remainder theorem ⓘ

ring theory → usesConcept → Chinese remainder theorem ⓘ

Euler’s theorem → relatedTo → Chinese remainder theorem ⓘ