Comparative Study of CRT and Extended Euclidean Algorithm in Solving Linear Diophantine Equations
DOI:
https://doi.org/10.64882/ijrt.v14.i2.1847Keywords:
linear Diophantine equation, Chinese remainder theorem, Extended Euclidean algorithm, Euclidean algorithm, Bézout’s identity.Abstract
Linear Diophantine equations are central to number theory and have wide-ranging applications in cryptography and computational mathematics. Among the classical methods for solving such equations, the Extended Euclidean Algorithm (EEA) and the Chinese Remainder Theorem (CRT) stand out as foundational approaches. The EEA is primarily used to compute greatest common divisors and modular inverses, making it effective for single-equation problems, while CRT provides a framework for solving systems of congruences with pairwise coprime moduli. This research project aims to conduct a comparative study of these two methods, focusing on their solvability conditions, computational efficiency, and practical applicability. The study will include theoretical analysis and algorithmic implementation to evaluate performance across varied problem sets. The expected outcome is a clear understanding of the strengths and limitations of each method, identifying contexts where one approach is more suitable than the other. This comparison will contribute to a deeper insight into algorithmic number theory and provide guidance for selecting appropriate techniques in mathematical and cryptographic applications.
References
Euclid. (1956). The thirteen books of Euclid’s Elements (T. L. Heath, Trans.). Dover Publications. (Original work published ca. 300 BCE)
Gauss, C. F. (1801/1966). Disquisitiones Arithmeticae (A. A. Clarke, Trans.). Yale University Press.
Hardy, G. H., & Wright, E. M. (2008). An introduction to the theory of numbers (6th ed.). Oxford University Press.
Ireland, K., & Rosen, M. (1990). A classical introduction to modern number theory (2nd ed.). Springer.
Burton, D. M. (2010). Elementary number theory (7th ed.). McGraw Hill Education.
Koblitz, N. (1994). A course in number theory and cryptography (2nd ed.). Springer.
Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison Wesley.
Bach, E., & Shallit, J. (1996). Algorithmic number theory, Volume I: Efficient algorithms. MIT Press.
Cohen, H. (1993). A course in computational algebraic number theory. Springer.
Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of applied cryptography. CRC Press.
Downloads
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
