Basic Maths Operations

Learn how to perform basic mathematical operations in programming, including square roots, prime numbers, factors, greatest common divisors, least common multiples, and modular arithmetic.
Written by: Brianna Laird
Last updated: December 2024

---

Mathematics is a fundamental part of programming, providing essential tools and methods that enable developers to solve complex problems efficiently. This guide explores a range of mathematical operations and demonstrates how to implement them effectively. In later tutorials, you’ll learn how to integrate these operations into your SplashKit projects to create programs, games and encrypted messaging applications.

Basic Maths Operations

This section introduces fundamental mathematical operations that are essential for programming. We’ll explore various mathematical functions and algorithms, starting with basic calculations like square roots and progressing to more complex operations like finding prime numbers and calculating greatest common divisors, least common multiples, and finding factors.

Square Root

The square root of a number is a value that, when multiplied by itself, gives the original number. For example, the square root of is since .

To calculate the square root efficiently, we use the Newton-Raphson method, an iterative numerical technique for finding roots of real-valued functions. This method starts with an initial estimate and repeatedly refines it using the formula:

Where:

• is the current estimate
• is the number we want to find the square root of
• is the improved estimate

This can be implemented in code as follows:

C++

double calculate_square_root(double x)
{
    double y;
    int p, square, c;

    // Find the first perfect square greater than the input number
    p = 0;
    do
    {
        p++;
        square = (p + 1) * (p + 1); // Calculate the next perfect square
    }
    while (x > square); // Stop when x is less than or equal to the square

    // Approximate the square root using the Newton-Raphson method
    y = (double)p;
    c = 0;
    while (c < 10) // Perform a maximum of 10 iterations
    {
        y = (x / y + y) / 2; // Update the guess by averaging x/y and y

        if (y * y == x) // Check if the square of the current guess matches the input
            return y; // If exact, return the square root

        c++;
    }

    return y;
}

C#

double CalculateSquareRoot(int x)
{
    double y = 0.0;
    int p = 0;
    int c = 0;

    // Find the first perfect square greater than the input number
    while (true)
    {
        p++;
        int square = (p + 1) * (p + 1); // Calculate the next perfect square
        if (x <= square) // Stop when x is less than or equal to the square
            break;
    }

    // Approximate the square root using the Newton-Raphson method
    y = (double)p;
    c = 0;
    while (c < 10) // Perform a maximum of 10 iterations
    {
        y = (x / y + y) / 2; // Update the guess by averaging x/y and y

        if (y * y == x) // Check if the square of the current guess matches the input
            return y; // If exact, return the square root

        c++;
    }

    return y;
}

Python

def calculate_square_root(x):
    # Find the first perfect square greater than the input number
    p = 0
    while True:
        p += 1
        square = (p + 1) * (p + 1)  # Calculate the next perfect square
        if x <= square:  # Stop when x is less than or equal to the square
            break

    # Approximate the square root using the Newton-Raphson method
    y = float(p)
    c = 0
    while c < 10:  # Perform a maximum of 10 iterations
        y = (x / y + y) / 2  # Update the guess by averaging x/y and y

        if y * y == x:  # Check if the square of the current guess matches the input
            return y  # If exact, return the square root

        c += 1

    return y

Tip

This could be useful for solving quadratic equations, calculating side lengths in right-angled triangles, or determining the magnitude of vectors in physics and mathematics.

Using this function

You can use the calculate_square_root function to find the square root of a number. For example, to calculate the square root of :

C++

double result = calculate_square_root(25);
std::cout << "The square root of 25 is: " << result << std::endl;

C#

double result = CalculateSquareRoot(25);
Console.WriteLine($"The square root of 25 is: {result}");

Python

result = calculate_square_root(25)
print(f"The square root of 25 is: {result}")

Expected Output

After running the above code, the expected output should be:

The square root of 25 is: 5.0

If we swapped the value to be instead of , the output would then be:

The square root of 23 is: 4.795831523312719

---

Prime Number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. To check if a number is prime, you will need to also calculate the square root of the number. You can use the following functions to check if a number is prime:

To check if a number is prime, we can use a simple algorithm that checks if the number is divisible by any number from 2 to its square root. The logic behind this approach is based on the following mathematical principles:

1. Any non-prime number can be written as a product of two factors:
2. If is not prime, at least one of these factors must be less than or equal to
3. If we can’t find any factors up to , then the number must be prime

This can be implemented in code as follows:

Note

This function relies on the calculate_square_root function defined above.

C++

bool is_the_number_prime(int n)
{
    if (n <= 1) return false;

    // Check if the number is divisible by any number from 2 to the square root of the number
    for (int i = 2; i <= calculate_square_root(n); i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

C#

bool IsTheNumberPrime(int n)
{
    if (n <= 1) return false;

    // Check if the number is divisible by any number from 2 to the square root of the number
    for (int i = 2; i <= CalculateSquareRoot(n); i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

Python

def is_the_number_prime(n):
    if n <= 1:
        return False

    # Check if the number is divisible by any number from 2 to the square root of the number
    for i in range(2, int(calculate_square_root(n)) + 1):
        if n % i == 0:
            return False
    return True

Tip

This could be useful in cryptography, generating unique identifiers, or finding factors of numbers in mathematics and computer science.

Using this function

You can use the is_the_number_prime function to check if a number is prime. For example, to check if is a prime number:

C++

bool is_prime = is_the_number_prime(17);
std::cout << "Is 17 a prime number? " << (is_prime ? "Yes" : "No") << std::endl;

C#

bool isPrime = IsTheNumberPrime(17);
Console.WriteLine($"Is 17 a prime number? {(isPrime ? "Yes" : "No")}");

Python

is_prime = is_the_number_prime(17)
print(f"Is 17 a prime number? {'Yes' if is_prime else 'No'}")

Expected Output

After running the above code, the expected output should be:

Is 17 a prime number? Yes

If we swapped the value to be instead of , the output would then be:

Is 24 a prime number? No

Finding Prime Numbers up to a Given Number

Finding prime numbers up to a given number is a common task in number theory and cryptography. The following function implements the Sieve of Eratosthenes algorithm, which efficiently finds all prime numbers up to a specified maximum . The algorithm works by:

1. Creating a list of numbers from 2 to
2. Starting with (the first prime), marking all multiples of up to as composite
3. Finding the next unmarked number and repeating step 2
4. The remaining unmarked numbers are prime

This can be expressed mathematically as finding all numbers where:

For example, to find primes up to 20, we would mark off:

• Multiples of 2:
• Multiples of 3:
• Multiples of 5: none remaining
• Leaving primes:

Note

This function relies on the is_the_number_prime function defined above.

C++

void find_prime_numbers_up_to(int limit)
{
    std::cout << "Prime numbers up to " << limit << ":";

    // Check all numbers up to the limit to see if they are prime
    for (int i = 2; i <= limit; i++)
    {
        if (is_the_number_prime(i))
        {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;
}

C#

void FindPrimeNumbersUpTo(int limit)
{
    Console.WriteLine($"Prime numbers up to {limit}:");

    // Check all numbers up to the limit to see if they are prime
    for (int i = 2; i <= limit; i++)
    {
        if (IsTheNumberPrime(i))
        {
            Console.Write($"{i} ");
        }
    }
    Console.WriteLine("");
}

Python

def find_prime_numbers_up_to(limit):
    print(f"Prime numbers up to {limit}:")

    # Check all numbers up to the limit to see if they are prime
    for i in range(2, limit + 1):
        if is_the_number_prime(i):
            print(f"{i} ")
    print("")

Tip

This could be useful for understanding number theory, building encryption algorithms, or solving problems in combinatorics.

Using this function

You can use the find_prime_numbers_up_to function to find all prime numbers up to a given limit. For example, to find prime numbers up to :

C++

find_prime_numbers_up_to(40);

C#

FindPrimeNumbersUpTo(40);

Python

find_prime_numbers_up_to(40)

Expected Output

After running the above code, the expected output should be:

Prime numbers up to 40:
2 3 5 7 11 13 17 19 23 29 31 37

Finding the Number of Divisors

The number of divisors of a positive integer is the count of positive integers that divide without leaving a remainder. We can find the number of divisors efficiently by only checking up to because divisors come in pairs.

For any divisor of , there exists a corresponding divisor such that . For example, for :

• When , we get
• When , we get
• When , we get

Therefore, except for perfect squares where , divisors occur in pairs. The total count can be calculated by:

where denotes that divides evenly.

Note

This function relies on the calculate_square_root function defined above.

C++

int count_divisors(int n)
{
    int count = 0;

    // Check all numbers up to the square root of n
    for (int i = 1; i <= calculate_square_root(n); i++)
    {
        if (n % i == 0)
        {
            // If divisors are equal, count only one
            if (n / i == i)
                count++;
            // Otherwise count both
            else
                count += 2;
        }
    }
    return count;
}

C#

int CountDivisors(int n)
{
    int count = 0;

    // Check all numbers up to the square root of n
    for (int i = 1; i <= CalculateSquareRoot(n); i++)
    {
        if (n % i == 0)
        {
            // If divisors are equal, count only one
            if (n / i == i)
                count++;
            // Otherwise count both
            else
                count += 2;
        }
    }
    return count;
}

Python

def count_divisors(n):
    count = 0

    # Check all numbers up to the square root of n
    for i in range(1, int(calculate_square_root(n)) + 1):
        if n % i == 0:
            # If divisors are equal, count only one
            if n // i == i:
                count += 1
            # Otherwise count both
            else:
                count += 2
    return count

Tip

This could be useful for solving problems in divisibility, determining properties of numbers, or analysing integer factorisation.

Using this function

You can use the count_divisors function to find the number of divisors of a given number. For example, to find the number of divisors of :

C++

int divisors = count_divisors(12);
std::cout << "The number of divisors of 12 is: " << divisors << std::endl;

C#

int divisors = CountDivisors(12);
Console.WriteLine($"The number of divisors of 12 is: {divisors}");

Python

divisors = count_divisors(12)
print(f"The number of divisors of 12 is: {divisors}")

Expected Output

After running the above code, the expected output should be:

The number of divisors of 12 is: 6

If we swapped the value to be instead of , the output would then be:

The number of divisors of 24 is: 8

Finding the Sum of Divisors

The sum of divisors of a positive integer is the sum of all positive integers that divide the number without leaving a remainder. This function calculates the sum of divisors of a given number by iterating through all numbers up to the square root of the input number and summing the divisors.

For a number , finding the sum of its divisors involves:

1. Iterating through numbers from 1 to
2. For each divisor , if is divisible by :
   • If , add once
   • Otherwise, add both and

For example, for :

• Divisors are: 1, 2, 3, 4, 6, 12
• Sum = 1 + 2 + 3 + 4 + 6 + 12 = 28

This can be expressed mathematically as:

where is 1 if condition is true, and 0 otherwise.

Note

This function relies on the calculate_square_root function defined above.

C++

int sum_divisors(int n)
{
    int sum = 0;

    // Check all numbers up to the square root of n
    for (int i = 1; i <= calculate_square_root(n); i++)
    {
        if (n % i == 0)
        {
            // If divisors are equal, add only one
            if (n / i == i)
                sum += i;
            // Otherwise add both
            else
                sum += i + n / i;
        }
    }
    return sum;
}

C#

int SumDivisors(int n)
{
    int sum = 0;

    // Check all numbers up to the square root of n
    for (int i = 1; i <= CalculateSquareRoot(n); i++)
    {
        if (n % i == 0)
        {
            // If divisors are equal, add only one
            if (n / i == i)
                sum += i;
            // Otherwise add both
            else
                sum += i + n / i;
        }
    }
    return sum;
}

Python

def sum_divisors(n):
    sum = 0

    # Check all numbers up to the square root of n
    for i in range(1, int(calculate_square_root(n)) + 1):
        if n % i == 0:
            # If divisors are equal, add only one
            if n // i == i:
                sum += i
            # Otherwise add both
            else:
                sum += i + n // i
    return sum

Tip

This could be useful in solving problems related to perfect numbers, amicable numbers, and understanding the properties of integers.

Using this function

You can use the sum_divisors function to find the sum of divisors of a given number. For example, to find the sum of divisors of :

C++

int sum = sum_divisors(12);
std::cout << "The sum of divisors of 12 is: " << sum << std::endl;

C#

int sum = SumDivisors(12);
Console.WriteLine($"The sum of divisors of 12 is: {sum}");

Python

sum = sum_divisors(12)
print(f"The sum of divisors of 12 is: {sum}")

Expected Output

After running the above code, the expected output should be:

The sum of divisors of 12 is: 28

If we swapped the value to be instead of , the output would then be:

The sum of divisors of 24 is: 60

Greatest Common Divisor

The greatest common divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The algorithm works by repeatedly dividing the larger number by the smaller number and replacing the larger number with the remainder until the remainder is zero. The last non-zero remainder is the GCD of the two numbers. This algorithm is known as the Euclidean algorithm which can be expressed mathematically as:

where represents the remainder when is divided by .

You can use the following functions to calculate the GCD of two numbers:

C++

int greatest_common_divisor(int a, int b)
{

    // Repeat the euclidean algorithm until the remainder is zero
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

C#

int GreatestCommonDivisor(int a, int b)
{

    // Repeat the euclidean algorithm until the remainder is zero
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Python

def greatest_common_divisor(a, b):

    # Repeat the euclidean algorithm until the remainder is zero
    while b != 0:
        temp = b
        b = a % b
        a = temp
    return a

Tip

This could be useful for simplifying fractions, solving Diophantine equations, cryptographic algorithms ,or analysing periodic patterns in mathematics and engineering.

Using this function

You can use the greatest_common_divisor function to find the GCD of two numbers. For example, to find the GCD of and :

C++

int gcd = greatest_common_divisor(24, 36);
std::cout << "The GCD of 24 and 36 is: " << gcd << std::endl;

C#

int gcd = GreatestCommonDivisor(24, 36);
Console.WriteLine($"The GCD of 24 and 36 is: {gcd}");

Python

gcd = greatest_common_divisor(24, 36)
print(f"The GCD of 24 and 36 is: {gcd}")

Expected Output

After running the above code, the expected output should be:

The GCD of 24 and 36 is: 12

If we swapped the value to be instead of , the output would then be:

The GCD of 24 and 15 is: 3

Least Common Multiple

The least common multiple (LCM) of two numbers is the smallest positive integer that is divisible by both of those numbers. An efficient way to calculate the LCM is by using the relationship between the LCM and the greatest common divisor (GCD) of those numbers. The formula for finding the LCM using the GCD is:

Note

This function relies on the greatest_common_divisor function defined above.

C++

int least_common_multiple(int a, int b)
{
    return abs(a * b) / greatest_common_divisor(a, b);
}

C#

int LeastCommonMultiple(int a, int b)
{
    return Math.Abs(a * b) / GreatestCommonDivisor(a, b);
}

Python

def least_common_multiple(a, b):
    return abs(a * b) // greatest_common_divisor(a, b)

Tip

This could be useful for finding synchronisation points in schedules, adding fractions with different denominators, or solving modular arithmetic problems.

Using this function

You can use the least_common_multiple function to find the LCM of two numbers. For example, to find the LCM of and :

C++

int lcm = least_common_multiple(24, 36);
std::cout << "The LCM of 24 and 36 is: " << lcm << std::endl;

C#

int lcm = LeastCommonMultiple(24, 36);
Console.WriteLine($"The LCM of 24 and 36 is: {lcm}");

Python

lcm = least_common_multiple(24, 36)
print(f"The LCM of 24 and 36 is: {lcm}")

Expected Output

After running the above code, the expected output should be:

The LCM of 24 and 36 is: 72

If we swapped the value to be instead of , the output would then be:

The LCM of 24 and 15 is: 120

Checking for Coprime Numbers

Two numbers are coprime (or relatively prime) if their greatest common divisor (GCD) is . For example, and are coprime because their GCD is , even though neither number is prime.

Note

This function relies on the greatest_common_divisor function defined above.

C++

bool are_coprime(int a, int b)
{
    return greatest_common_divisor(a, b) == 1;
}

C#

bool AreCoprime(int a, int b)
{
    return GreatestCommonDivisor(a, b) == 1;
}

Python

def are_coprime(a, b):
    return greatest_common_divisor(a, b) == 1

Tip

This could be useful for cryptographic algorithms, modular arithmetic, or simplifying problems involving fractions

Using this function

You can use the are_coprime function to check if two numbers are coprime. For example, to check if and are coprime:

C++

bool coprime = are_coprime(8, 15);
std::cout << "Are 8 and 15 coprime? " << (coprime ? "Yes" : "No") << std::endl;

C#

bool coprime = AreCoprime(8, 15);
Console.WriteLine($"Are 8 and 15 coprime? {(coprime ? "Yes" : "No")}");

Python

coprime = are_coprime(8, 15)
print(f"Are 8 and 15 coprime? {'Yes' if coprime else 'No'}")

Expected Output

After running the above code, the expected output should be:

Are 8 and 15 coprime? Yes

If we swapped the value to be instead of , the output would then be:

Are 8 and 12 coprime? No

Finding All Coprime Numbers

Finding all numbers that are coprime to a given value is useful in many mathematical applications, particularly in cryptography and number theory. The following function identifies all numbers that are coprime to an input value up to a specified maximum. Two numbers are coprime if their greatest common divisor (GCD) is .

For example, if we want to find all numbers coprime to up to , we would get:

Note

This function relies on the are_coprime function defined above.

C++

void find_coprimes_up_to(int n, int max)
{
    std::cout << "Numbers coprime to " << n << " up to " << max << ":";

    // Check all numbers up to the maximum
    for (int i = 1; i <= max; i++)
    {
        if (are_coprime(n, i))
        {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;
}

C#

void FindCoprimesUpTo(int n, int max)
{
    Console.WriteLine($"Numbers coprime to {n} up to {max}:");

    // Check all numbers up to the maximum
    for (int i = 1; i <= max; i++)
    {
        if (AreCoprime(n, i))
        {
            Console.Write($"{i} ");
        }
    }
    Console.WriteLine("");
}

Python

def find_coprimes_up_to(n, max):
    print(f"Numbers coprime to {n} up to {max}:")

    # Check all numbers up to the maximum
    for i in range(1, max + 1):
        if are_coprime(n, i):
            write(f"{i} ")
    print("")

Tip

This could be useful in modular arithmetic, number theory, and creating encryption keys in cryptography.

Using this function

You can use the find_coprimes_up_to function to find all numbers coprime to a given value up to a specified maximum. For example, to find all numbers coprime to up to :

C++

find_coprimes_up_to(12, 20);

C#

FindCoprimesUpTo(12, 20);

Python

find_coprimes_up_to(12, 20)

Expected Output

After running the above code, the expected output should be:

Numbers coprime to 12 up to 20:
1 5 7 11 13 17 19

If we swapped the value to be instead of , the output would then be:

Numbers coprime to 15 up to 20:
1 2 4 7 8 11 13 14 16 17 19

Eulers Totient Function

Euler’s totient function, denoted as , is a mathematical function that counts the number of positive integers less than or equal to that are coprime to . For example, because the numbers and are coprime to .

The totient function can be calculated using the formula:

Where:

• denotes that divides evenly
• The product is taken over all prime factors of
• The formula can be simplified to:

This can be implemented in code as follows:

Note

This function relies on the calculate_square_root function defined above.

C++

int euler_totient_function(int n)
{
    int result = n;

    // Check all numbers up to the square root of n
    for (int i = 2; i <= calculate_square_root(n); i++)
    {
        if (n % i == 0)
        {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }

    if (n > 1)
        result -= result / n;

    return result;
}

C#

int EulerTotientFunction(int n)
{
    int result = n;

    // Check all numbers up to the square root of n
    for (int i = 2; i <= CalculateSquareRoot(n); i++)
    {
        if (n % i == 0)
        {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }

    if (n > 1)
        result -= result / n;

    return result;
}

Python

def euler_totient_function(n):
    result = n

    # Check all numbers up to the square root of n
    for i in range(2, int(calculate_square_root(n)) + 1):
        if n % i == 0:
            while n % i == 0:
                n //= i
            result -= result // i

    if n > 1:
        result -= result // n

    return result

Tip

This could be useful for solving problems in number theory, or in cryptographic algorithms such as the RSA encryption scheme.

Using this function

You can use the euler_totient_function to find the totient function of a given number. For example, to find :

C++

int result = euler_totient_function(12);
std::cout << "The Euler's totient function of 12 is: " << result << std::endl;

C#

int result = EulerTotientFunction(12);
Console.WriteLine($"The Euler's totient function of 12 is: {result}");

Python

result = euler_totient_function(12)
print(f"The Euler's totient function of 12 is: {result}")

Expected Output

After running the above code, the expected output should be:

The Euler's totient function of 12 is: 4

If we swapped the value to be instead of , the output would then be:

The Euler's totient function of 24 is: 8

Finding Factors

A factor is a number that divides evenly into another number with no remainder. For example, the factors of are and . Finding factors is useful in various mathematical applications, including:

• Simplifying fractions
• Finding common divisors
• Breaking down numbers into their prime factorisation

The following function finds all factors of a given number by checking all potential divisors up to the input number:

C++

void find_factors(int n)
{
    std::cout << "Factors of " << n << ": ";

    // Check all potential divisors up to n
    for (int i = 1; i <= n; i++)
    {
        if (n % i == 0)
        {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;
}

C#

void FindFactors(int n)
{
    Console.WriteLine($"Factors of {n}:");

    // Check all potential divisors up to n
    for (int i = 1; i <= n; i++)
    {
        if (n % i == 0)
        {
            Console.Write($"{i} ");
        }
    }
    Console.WriteLine("");
}

Python

def find_factors(n):
    print(f"Factors of {n}:")

    # Check all potential divisors up to n
    factors = [i for i in range(1, n + 1) if n % i == 0]
    print(" ".join(map(str, factors)))
    print("")

Tip

This could be useful for understanding the structure of integers, solving polynomial equations, or optimising divisibility problems.

Using this function

You can use the find_factors function to find all factors of a given number. For example, to find all factors of :

C++

find_factors(24);

C#

FindFactors(24);

Python

find_factors(24)

Expected Output

After running the above code, the expected output should be:

Factors of 24:
1 2 3 4 6 8 12 24

If we swapped the value to be instead of , the output would then be:

Factors of 15:
1 3 5 15

Finding Prime Factors

The prime factorisation of a number is its decomposition into a product of prime numbers. For example, can be written as . The following function identifies all prime factors of a given number by:

1. First extracting all factors of (the smallest prime number)
2. Then checking odd numbers up to the square root for remaining factors
3. If any number remains after this process, it must be a prime factor itself

C++

void find_prime_factors(int n)
{
    std::cout << "Prime factors of " << n << ": ";

    // Extract all factors of 2
    while (n % 2 == 0)
    {
        std::cout << "2 ";
        n /= 2;
    }

    // Check odd numbers up to square root
    for (int i = 3; i * i <= n; i += 2)
    {
        while (n % i == 0)
        {
            std::cout << i << " ";
            n /= i;
        }
    }

    // If n is still greater than 2, it's a prime factor
    if (n > 2)
        std::cout << n;

    std::cout << std::endl;
}

C#

void FindPrimeFactors(int n)
{
    Console.WriteLine($"Prime factors of {n}:");

    // Extract all factors of 2
    while (n % 2 == 0)
    {
        Write("2 ");
        n /= 2;
    }

    // Check odd numbers up to square root
    for (int i = 3; i * i <= n; i += 2)
    {
        while (n % i == 0)
        {
            Write($"{i} ");
            n /= i;
        }
    }

    // If n is still greater than 2, it's a prime factor
    if (n > 2)
        Write(n);

    Console.WriteLine("");
}

Python

def find_prime_factors(n):
    print(f"Prime factors of {n}:")

    # Extract all factors of 2
    while n % 2 == 0:
        write("2 ")
        n //= 2

    # Check odd numbers up to square root
    for i in range(3, int(n**0.5) + 1, 2):
        while n % i == 0:
            write(f"{i} ")
            n //= i

    # If n is still greater than 2, it's a prime factor
    if n > 2:
        write(str(n))

    print("")

Tip

This could be useful for cryptographic key generation, determining the uniqueness of numbers, or solving problems in number theory.

Using this function

You can use the find_prime_factors function to find all prime factors of a given number. For example, to find all prime factors of :

C++

find_prime_factors(24);

C#

FindPrimeFactors(24);

Python

find_prime_factors(24)

Expected Output

After running the above code, the expected output should be:

Prime factors of 24:
2 2 2 3

If we swapped the value to be instead of , the output would then be:

Prime factors of 15:
3 5

Checking Congruence

Two numbers and are considered congruent modulo if they yield the same remainder when divided by . This relationship is written mathematically as:

For example, because both numbers leave a remainder of when divided by .

We can implement a function to check if two numbers are congruent modulo as follows:

C++

bool is_congruent(int a, int b, int mod) {
    return (a % mod) == (b % mod);
}

C#

bool IsCongruent(int a, int b, int mod) {
    return (a % mod) == (b % mod);
}

Python

def is_congruent(a, b, mod):
    return (a % mod) == (b % mod)

Tip

This could be useful for modular arithmetic, solving problems in computer science algorithms, or verifying conditions in cryptography.

Using this function

You can use the is_congruent function to check if two numbers are congruent modulo . For example, to check if and are congruent modulo :

C++

bool congruent = is_congruent(38, 14, 12);
std::cout << "Are 38 and 14 congruent modulo 12? " << (congruent ? "Yes" : "No") << std::endl;

C#

bool congruent = IsCongruent(38, 14, 12);
Console.WriteLine($"Are 38 and 14 congruent modulo 12? {(congruent ? "Yes" : "No")}");

Python

congruent = is_congruent(38, 14, 12)
print(f"Are 38 and 14 congruent modulo 12? {'Yes' if congruent else 'No'}")

Expected Output

After running the above code, the expected output should be:

Are 38 and 14 congruent modulo 12? Yes

If we swapped the value to be instead of , the output would then be:

Are 38 and 15 congruent modulo 12? No

Modular Arithmetic Operations

Modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” upon reaching a certain value—the modulus. This section includes functions for modular addition, subtraction, multiplication, and exponentiation. The function modular_exponentiation performs modular exponentiation, which raises a base to an exponent under a modulus efficiently. This operation is commonly used in cryptography and number theory.

Tip

Modular arithmetic can be useful for solving problems involving cycles, such as clock calculations or repeating patterns. It’s also fundamental in cryptography, computer science algorithms, and number theory.

Modular Addition

Modular addition is the operation of adding two numbers and taking the remainder when divided by a modulus. This operation is useful in many applications, including cryptography and computer science.

Mathematically, modular addition can be expressed as:

where:

• and are the numbers to be added
• is the modulus
• denotes the modulo operation, which finds the remainder after division of one number by another

For example, if we want to add and with a modulus of , we calculate:

This means that and add up to , and when we take the remainder after dividing by , we get .

This can be implemented in code as follows:

C++

int modular_addition(int a, int b, int mod) {
    return (a + b) % mod;
}

C#

int ModularAddition(int a, int b, int mod) {
    return (a + b) % mod;
}

Python

def modular_addition(a, b, mod):
    return (a + b) % mod

Using this function

You can use the modular_addition function to perform modular addition of two numbers. For example, to add and with a modulus of :

C++

int result = modular_addition(7, 5, 10);
std::cout << "The result of modular addition is: " << result << std::endl;

C#

int result = ModularAddition(7, 5, 10);
Console.WriteLine($"The result of modular addition is: {result}");

Python

result = modular_addition(7, 5, 10)
print(f"The result of modular addition is: {result}")

Expected Output

After running the above code, the expected output should be:

The result of modular addition is: 2

If we swapped the value to be instead of , the output would then be:

The result of modular addition is: 2

Modular Subtraction

Modular subtraction is the operation of subtracting two numbers and taking the remainder when divided by a modulus. This operation is useful in many applications, including cryptography and computer science.

Mathematically, modular subtraction can be expressed as:

where:

• and are the numbers to be subtracted
• is the modulus
• denotes the modulo operation, which finds the remainder after division of one number by another

For example, if we want to subtract from with a modulus of , we calculate:

This means that minus is , and when we take the remainder after dividing by , we get .

This can be implemented in code as follows:

C++

int modular_subtraction(int a, int b, int mod) {
    return (a - b + mod) % mod;
}

C#

int ModularSubtraction(int a, int b, int mod) {
    return (a - b + mod) % mod;
}

Python

def modular_subtraction(a, b, mod):
    return (a - b + mod) % mod

Using this function

You can use the modular_subtraction function to perform modular subtraction of two numbers. For example, to subtract from with a modulus of :

C++

int result = modular_subtraction(7, 5, 10);
std::cout << "The result of modular subtraction is: " << result << std::endl;

C#

int result = ModularSubtraction(7, 5, 10);
Console.WriteLine($"The result of modular subtraction is: {result}");

Python

result = modular_subtraction(7, 5, 10)
print(f"The result of modular subtraction is: {result}")

Expected Output

After running the above code, the expected output should be:

The result of modular subtraction is: 2

If we swapped the value to be instead of , the output would then be:

The result of modular subtraction is: 3

Modular Multiplication

Modular multiplication is the operation of multiplying two numbers and taking the remainder when divided by a modulus. This operation is useful in many applications, including cryptography and computer science.

Mathematically, modular multiplication can be expressed as:

where:

• and are the numbers to be multiplied
• is the modulus
• denotes the modulo operation, which finds the remainder after division of one number by another

For example, if we want to multiply and with a modulus of , we calculate:

This means that multiplied by is , and when we take the remainder after dividing by , we get .

This can be implemented in code as follows:

C++

int modular_multiplication(int a, int b, int mod) {
    return (a * b) % mod;
}

C#

int ModularMultiplication(int a, int b, int mod) {
    return (a * b) % mod;
}

Python

def modular_multiplication(a, b, mod):
    return (a * b) % mod

Using this function

You can use the modular_multiplication function to perform modular multiplication of two numbers. For example, to multiply and with a modulus of :

C++

int result = modular_multiplication(7, 5, 10);
std::cout << "The result of modular multiplication is: " << result << std::endl;

C#

int result = ModularMultiplication(7, 5, 10);
Console.WriteLine($"The result of modular multiplication is: {result}");

Python

result = modular_multiplication(7, 5, 10)
print(f"The result of modular multiplication is: {result}")

Expected Output

After running the above code, the expected output should be:

The result of modular multiplication is: 5

If we swapped the value to be instead of , the output would then be:

The result of modular multiplication is: 5

Modular Exponentiation

Modular exponentiation is the operation of raising a base to an exponent and taking the remainder when divided by a modulus. This operation is useful in many applications, including cryptography and computer science.

Mathematically, modular exponentiation can be expressed as:

where:

• is the number to be raised to the power
• is the power to which the base is raised
• is the modulus
• denotes the modulo operation, which finds the remainder after division of one number by another

For example, if we want to calculate with a modulus of , we calculate:

This means that raised to the power of is , and when we take the remainder after dividing by , we get .

This can be implemented in code as follows:

C++

int modular_exponentiation(int base, int exponent, int mod) {
    int result = 1;
    base = base % mod;

    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        exponent >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

C#

int ModularExponentiation(int base, int exponent, int mod) {
    int result = 1;
    base = base % mod;

    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        exponent >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

Python

def modular_exponentiation(base, exponent, mod):
    result = 1
    base = base % mod

    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % mod
        exponent >>= 1
        base = (base * base) % mod
    return result

Using this function

You can use the modular_exponentiation function to perform modular exponentiation of a base to an exponent. For example, to calculate with a modulus of :

C++

int result = modular_exponentiation(3, 4, 5);
std::cout << "The result of modular exponentiation is: " << result << std::endl;

C#

int result = ModularExponentiation(3, 4, 5);
Console.WriteLine($"The result of modular exponentiation is: {result}");

Python

result = modular_exponentiation(3, 4, 5)
print(f"The result of modular exponentiation is: {result}")

Expected Output

After running the above code, the expected output should be:

The result of modular exponentiation is: 1

If we swapped the value to be instead of , the output would then be:

The result of modular exponentiation is: 4

Summary

This guide covered various mathematical utilities and functions that are commonly used in programming and discrete mathematics. You learned how to implement functions for finding the greatest common divisor (GCD), least common multiple (LCM), coprime numbers, factors, prime factors, and modular arithmetic operations. These functions are essential for solving mathematical problems, cryptography, and number theory. By understanding and implementing these functions, you can enhance your programming skills and solve a wide range of mathematical problems efficiently. You can use this knowledge to build more complex algorithms and applications that require mathematical computations.