(Practice) Modular Arithmetic

Multiplicative Inverse

import java.util.*;

public class MultiplicativeInverse {
	private static int[] extendedGCD(int a, int b) {
        	if (a == 0) {
            		return new int[]{b, 0, 1};
        	}

        	int[] result = extendedGCD(b % a, a);
        	int g = result[0];
        	int x1 = result[1];
        	int y1 = result[2];
        	int x = y1 - (b / a) * x1;
        	int y = x1;

		return new int[]{g, x, y};
	}

	private static int findModularInverse(int a, int n) {
		int[] result = extendedGCD(a, n);
		int gcd = result[0];
		int x = result[1];

		if (gcd != 1)
			return -1;
		else
			return (x % n + n) % n;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		System.out.print("Enter the number (a): ");
		int a = scanner.nextInt();
		System.out.print("Enter the modulus (n): ");
		int n = scanner.nextInt();

		int inverse = findModularInverse(a, n);

		if (inverse == -1)
			System.out.println("No solution exists.");
		else
			System.out.println("The solution for " + a + " modulo " + n + " is: " + inverse);

		scanner.close();
	}
}

Enter the number (a): 10
Enter the modulus (n): 2
No solution exists.

Enter the number (a): 3
Enter the modulus (n): 11
The solution for 3 modulo 11 is: 4

Prime Factorization

import java.util.*;

public class PrimeFactorization {
	private static void primeFactors(int number) {
		if (number <= 1) {
			System.out.println("Number should be greater than 1.");
			return;
		}

		while (number % 2 == 0) {
			System.out.print(2 + " ");
			number /= 2;
		}

		for (int i = 3; i * i <= number; i++) {
			while (number % i == 0) {
				System.out.print(i + " ");
				number /= i;
			}
		}

		if (number > 2) {
			System.out.print(number);
		}

		System.out.println();
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		System.out.print("Enter the number: ");
		int number = scanner.nextInt();
		System.out.println("Prime factors of " + number + " are:");

		primeFactors(number);

		scanner.close();
	}
}

Enter the number: 60
Prime factors of 60 are:
2 2 3 5