Chinese Remainder Theorem in Java

Chinese Remainder Theorem in Java : 

The Chinese Remainder Theorem (CRT) is a mathematical theorem that has applications in various fields, including programming and cryptography. In programming, the Chinese Remainder Theorem is often used to solve a system of modular congruences efficiently. It finds a unique solution to a set of congruences based on their remainders and divisors.

Java code :

import java.util.Scanner;

class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        

        System.out.println("Enter size of the array: ");

        int size = sc.nextInt();

        int[] div = new int[size];

        

        System.out.println("Enter the elements in the divisor array: ");

        for (int i = 0; i < size; i++) {

            div[i] = sc.nextInt();

        }

        

        System.out.println("Enter the elements in the remainder array: ");

        int[] rim = new int[size];

  

        for (int i = 0; i < size; i++) {

            rim[i] = sc.nextInt();

        }

        

        int j, x = 1;

        

        while (true) {

            for (j = 0; j < size; j++) {

                if (x % div[j] != rim[j]) {

                    break;

                }

            }

            

            if (j == size) {

                System.out.println("The number is: " + x);

                break;

            }

            x++;

        }

    }

}

Explanation : 

1. `import java.util.Scanner;`: This line imports the `Scanner` class from the `java.util` package. The `Scanner` class is used to read user input from the console.

2. `class Main { ... }`: This is the main class of the Java program. The program starts its execution from the `main` method inside this class.

3. `public static void main(String[] args) { ... }`: This is the main method, the entry point of the program. It takes an array of `String` arguments (`args`), but in this code, it is not utilized.

4. `Scanner sc = new Scanner(System.in);`: This creates a new `Scanner` object named `sc`, which will be used to read input from the user.

5. `System.out.println("Enter size of the array : ");`: This line displays a prompt to the user, asking them to enter the size of the arrays they will input.

6. `int size = sc.nextInt();`: This line reads an integer value entered by the user and stores it in the variable `size`. This value represents the size of the arrays that the user will input.

7. `int[] div = new int[size];`: This line declares an integer array `div` with a size equal to the value provided by the user.

8. `System.out.println("Enter the elements in the divisor array : ");`: This line prompts the user to enter the elements of the divisor array.

9. `for (int i = 0; i < size; i++) { ... }`: This loop reads `size` number of integers entered by the user and stores them in the `div` array.

10. `int[] rim = new int[size];`: This line declares another integer array `rim` with the same size as the `div` array.

11. `System.out.println("Enter the elements in the remainder array : ");`: This line prompts the user to enter the elements of the remainder array.

12. `for (int i = 0; i < size; i++) { ... }`: Similar to the previous loop, this loop reads `size` number of integers entered by the user and stores them in the `rim` array.

13. `int j, x = 1;`: Two integer variables, `j` and `x`, are declared. `x` is initialized to 1, and `j` will be used for loop control later.

14. `while (true) { ... }`: This starts an infinite loop that will continue until a `break` statement is executed inside the loop.

15. `for (j = 0; j < size; j++) { ... }`: This loop iterates through each element of the `div` and `rim` arrays to check if the value of `x` is divisible by each `div[j]` and gives the remainder `rim[j]`.

16. `if (j == size) { ... }`: If the loop completes without any break, it means `x` satisfies all the conditions for being divisible by each element of the `div` array with the respective remainders from the `rim` array.

17. `System.out.println("The number is : " + x);`: The value of `x` is printed as the output, representing the number that meets the given conditions.

18. `break;`: This statement is reached when a suitable `x` has been found, and the loop is exited using the `break` statement.

19. `x++;`: If the conditions are not satisfied, `x` is incremented, and the loop continues to find the next number that satisfies the conditions.

The program stops execution after finding and printing the number that fulfills all the conditions specified by the user. If no such number is found, the program continues running until a suitable number is found or the user stops the program manually.