HYBRIDIZING HENSEL’S LEMMA, FUNDAMENTAL THEOREM OF ARITHMETIC, AND CHINESE REMAINDER THEOREM FOR SOLVING POLYNOMIAL CONGRUENCES
Abstract
Polynomial congruence can be solved by applying Hensel’s Lemma. However, Hensel’s Lemma itself does not apply to solving generalized polynomial congruences. The purpose of this research is to determine the recursive formula for the solution of polynomial congruence modulo prime numbers and to construct a general solution algorithm of polynomial congruence modulo arbitrary positive integers. Unlike previous studies, this research proposes the recursive hybrid algorithm combining Hensel’s Lemma, the Fundamental Theorem of Arithmetic, and the Chinese Remainder Theorem, highlighting the originality of the approach in extending its application beyond prime power moduli. The result of this research is the form of a recursive formula for the solution of polynomial congruence modulo prime numbers and the algorithm for solving polynomial congruence modulo arbitrary positive integers using the combination of Hensel’s Lemma, Fundamental Theorem of Arithmetic, and Chinese Remainder Theorem. The results of this research contribute to the development of mathematical methods, especially in the field of number theory. However, the applicability of the recursive formula is limited to cases where the conditions of Hensel’s Lemma are satisfied, that is, when a solution of the polynomial modulo a prime is such that the polynomial equals zero while its derivative does not equal zero modulo the same prime. Extending the method to situations where this condition fails remains a subject for future research.
Downloads
References
P. S. Rudman, HOW MATHEMATICS HAPPENED: THE FIRST 50,000 YEARS. New York: Prometheus Books, 2007.
M. Lemma and D. Allard, “APPLICATIONS OF CONGRUENCE TO DIVISIBILITY THEORY,” IJRDO-Journal Math., vol. 3, no. 11, pp. 32–42, 2017.
G. Knapp, “POLYNOMIAL ROOT DISTRIBUTION AND ITS IMPACT ON SOLUTIONS TO THUE EQUATIONS,” Ph.D. dissertation, University of Oregon, 2023.
J. Bayer, M. David, B. Stock, A. Pal, Y. Matiyasevich, and D. Schleicher, “DIOPHANTINE EQUATIONS AND THE DPRM THEOREM,” Arch. Form. Proofs, 2022.
B. Grechuk, “DIOPHANTINE EQUATIONS: A SYSTEMATIC APPROACH,” 2021, [Online]. Available: https://arxiv.org/abs/2108.08705
O. Ikponmwosa-Eweka and A. Ozigagun, “APPLICATION OF RESPONSE SURFACE METHODOLOGY (RSM) TO PREDICT PENETRATION AREA DURING TIG WELDING AT STEADY STATE CONDITION,” NIPES - J. Sci. Technol. Res., vol. 5, no. 3, pp. 94 – 100, 2023.
A. A. Kostoglotov, I. V Kalienko, A. S. Kornev, and S. V Lazarenko, “SYNTHESIS OF ALGORITHMS FOR COMPENSATING SYSTEMATIC ERRORS BASED ON THE CONSTRUCTION OF POLYNOMIAL MATHEMATICAL MODELS OF RADAR MEASUREMENTS,” Meas. Tech., vol. 65, no. 4, pp. 290 – 296, 2022. doi: https://doi.org/10.1007/s11018-022-02081-w
M. Pagano, I. Tananko, and E. Stankevich, “ON THE OPTIMAL INPUT RATE IN QUEUES WITH BATCH SERVICE,” Axioms, vol. 12, no. 7, 2023.doi: https://doi.org/10.3390/axioms12070656
M. Schroeder, NUMBER THEORY IN SCIENCE AND COMMUNICATION: WITH APPLICATIONS IN CRYPTOGRAPHY, PHYSICS, DIGITAL INFORMATION, COMPUTING, AND SELF-SIMILARITY, 5th ed. Berlin: Springer-Verlag, 2009.
A. Mosunov, “ABSOLUTE BOUND ON THE NUMBER OF SOLUTIONS OF CERTAIN DIOPHANTINE EQUATIONS OF THUE AND THUE-MAHLER TYPE,” 2022, [Online]. Available: https://arxiv.org/abs/2206.13653
A. Gherga and S. Siksek, “EFFICIENT RESOLUTION OF THUE-MAHLER EQUATIONS,” 2022, [Online]. Available: https://arxiv.org/abs/2207.14492
T. Chinburg, B. Hemenway, N. Heninger, and Z. Scherr, “CRYPTOGRAPHIC APPLICATIONS OF CAPACITY THEORY: ON THE OPTIMALITY OF COPPERSMITH’S METHOD FOR UNIVARIATE POLYNOMIALS,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 10031 LNCS, pp. 759 – 788, 2016. doi: https://doi.org/10.1007/978-3-662-53887-6_28
R. K. Koppanati and K. Kumar, “P-MEC: POLYNOMIAL CONGRUENCE-BASED MULTIMEDIA ENCRYPTION TECHNIQUE OVER CLOUD,” IEEE Consum. Electron. Mag., vol. 10, no. 5, pp. 41 – 46, 2021. doi: https://doi.org/10.1109/MCE.2020.3003127
K. Bibak, B. M. Kapron, and V. Srinivasan, “AUTHENTICATION OF VARIABLE LENGTH MESSAGES IN QUANTUM KEY DISTRIBUTION,” EPJ Quantum Technol., vol. 9, no. 1, 2022. doi: https://doi.org/10.1140/epjqt/s40507-022-00127-0
G. Ghosal, “A STUDY ON THE DEVELOPMENT AND APPLICATION OF NUMBER THEORY IN ENGINEERING FIELD,” Int. J. Inf. Sci. Comput., vol. 7, pp. 109–114, 2020. doi: https://doi.org/10.30954/2348-7437.2.2020.5
H. H. Chan and K. Chen, “THE FUNDAMENTAL THEOREM OF ARITHMETIC AND Q-SERIES,” Math. Mag., vol. 97, pp. 187–193, 2024. doi: https://doi.org/10.1080/0025570X.2024.2312094
I. Ahmad, B. Lee, and S. Shin, “ANALYSIS OF CHINESE REMAINDER THEOREM FOR DATA COMPRESSION,” in Proc. Int. Conf. Inf. Netw., Barcelona, 2020. doi: https://doi.org/10.1109/ICOIN48656.2020.9016442
E. A. Alhassan et al., “ON SOME ALGEBRAIC PROPERTIES OF THE CHINESE REMAINDER THEOREM WITH APPLICATIONS TO REAL LIFE,” J. Appl. Math. Comput., vol. 5, pp. 219–224, 2021. doi: https://doi.org/10.26855/jamc.2021.09.008
I. Weiss, “SURVEY ARTICLE: THE REAL NUMBERS–A SURVEY OF CONSTRUCTIONS,” Rocky Mt. J. Math., vol. 45, pp. 737–762, 2015. doi: https://doi.org/10.1216/RMJ-2015-45-3-737
F. Q. Gouvêa, P-ADIC NUMBERS: AN INTRODUCTION. Berlin: Springer, 2020. doi: https://doi.org/10.1007/978-3-030-47295-5
J. Gallian, Contemporary abstract algebra, 10th ed. London: Chapman and Hall/CRC, 2021. doi: https://doi.org/10.1201/9781003142331
K. H. Rosen, ELEMENTARY NUMBER THEORY AND ITS APPLICATIONS, 7th ed. London: Pearson, 2023.
D. M. Burton, ELEMENTARY NUMBER THEORY, 7th ed. New York: McGraw-Hill, 2010.
Copyright (c) 2025 Eka Oktaviansyah, Edi Kurniadi, Dianne Amor Kusuma
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
