Implementation of Chinese Remainder Theorem with Extended Euclidean Algorithm

[mn121mn121]

This pull request implements the Chinese Remainder Theorem (CRT) in Java, providing an efficient solution to find an integer 𝑥 that satisfies multiple simultaneous congruences. The implementation uses the Extended Euclidean Algorithm to compute modular inverses, significantly improving performance for larger inputs.

Problem Statement: Given several pairwise coprime moduli (n1, n2, ..., nk) and integers reaminders (a1, a2, ..., ak), the goal is to find an integer x such that:

x ≡ a1 (mod n1) x ≡ a2 (mod n2) ... x ≡ ak (mod nk)

Implementation Details: The code computes the product of all moduli. For each modulus, it calculates the corresponding Ni and its modular inverse using the Extended Euclidean Algorithm. It sums the contributions from each equation to find the result.

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized it.
• [x] All filenames are in PascalCase.
• [x] All functions and variable names follow Java naming conventions.
• [ ] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
• [ ] All new code is formatted with clang-format -i --style=file path/to/your/file.java

[codecov-commenter]

Codecov Report

Attention: Patch coverage is 0% with 34 lines in your changes missing coverage. Please review.

Project coverage is 66.60%. Comparing base (dfff8d9) to head (4f213a7). Report is 1 commits behind head on master.

Files with missing lines	Patch %	Lines
...m/thealgorithms/maths/ChineseRemainderTheorem.java	0.00%	34 Missing :warning:

Additional details and impacted files

@@             Coverage Diff              @@
##             master    #5872      +/-   ##
============================================
- Coverage     66.74%   66.60%   -0.14%     
  Complexity     4489     4489              
============================================
  Files           610      611       +1     
  Lines         16929    16963      +34     
  Branches       3267     3272       +5     
============================================
  Hits          11299    11299              
- Misses         5182     5216      +34     
  Partials        448      448              

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[siriak]

It's already present here https://github.com/TheAlgorithms/Java/blob/b0cef5b571965aed5410a61531ddf1e1cb5c2608/src/main/java/com/thealgorithms/maths/ChineseRemainderTheorem.java#L13