Prime Numbers Complete

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Prime numbers are the building blocks of all natural numbers because every number can be expressed as a product of primes.

The steps to determine if a number \(n\) is prime are as follows:

1. Check divisibility by 2: If \(n\) is even and greater than 2, it is not prime.

2. Check divisibility by odd numbers: Test if \(n\) is divisible by any odd number from 3 up to \(\sqrt{n}\).

3. Prime if no divisors found: If no divisors other than 1 and \(n\) are found, then \(n\) is prime.

For example, to check if 29 is a prime number:

1. 29 is not even.

2. Check divisibility by odd numbers up to \(\sqrt{29} \approx 5.39\) (i.e., check 3 and 5).

3. 29 is not divisible by 3 or 5.

4. Therefore, 29 is a prime number.

import sympy as sp
from sympy import *
from math import gcd

Introduction to Prime Numbers

Checking if number is prime or not

To check if a number is prime or not, we need to check if it is divisible by any number other than 1 and itself. We can do this by iterating over all numbers from 2 to the square root of the number and checking if the number is divisible by any of them. If the number is divisible by any number other than 1 and itself, then it is not prime.

def is_prime(n):
    if n <= 1:
        print(f"The number {n} is not prime")
        return False
    for i in range(2, int(sp.sqrt(n)) + 1):
        if n % i == 0:
            print(f"The number {n} is not prime")
            return False
    print(f"The number {n} is prime")
    return True

Explanation

Checking if \(6\) is Prime:

1. \(6\) is even.

2. Since $\( is greater than \)2$ and even, it is not a prime number.

n = 69769
is_prime(n)

The number 69769 is not prime

False

Explanation

Checking if \(69769\) is Prime:

1. \(69769\) is not even.

2. Calculate \(\sqrt{69769} \approx 264.17\). Check for divisibility by odd numbers up to \(264\).

3. \(69769\) is divisible by \(263\):

\[ 69769 \div 263 = 265 \]

n = 83
is_prime(n)

The number 83 is prime

True

Explanation

Checking if 83 is Prime:

1. 83 is not even.

2. Calculate \(\sqrt{83} \approx 9.11\). Check for divisibility by odd numbers up to \(9\).

3. \(83\) is not divisible by \(3, 5, or 7\).

4. Therefore, \(83\) is a prime number.

n = 983
is_prime(n)

The number 983 is prime

True

Explanation

Checking if \(983\) is Prime:

1. \(983\) is not even.

2. Calculate \(\sqrt{983} \approx 31.36\). Check for divisibility by odd numbers up to \(31\).

3. \(983\) is not divisible by \(3, 5, 7, 11, 13, 17, 19, 23, 29, or 31\).

4. Therefore, \(983\) is a prime number.

Generating Prime Numbers

To generate a random prime number, we can generate a random number and check if it is prime using the method described above. If the number is not prime, we can generate another random number and repeat the process until we find a prime number.

With this function, we can actually specify the range of prime numbers we want to generate. For example, if we want to generate a prime number between 1 and 20, we can specify this in the generate prime function.

def generate_prime_number(start=1000, end=10000):
    while True:
        n = random.randint(start,end)
        if is_prime(n):
            return n

p = generate_prime_number(1000,10000)
print(f"p = {p}")

The number 3939 is not prime
The number 6812 is not prime
The number 4209 is not prime
The number 5468 is not prime
The number 1843 is not prime
The number 5847 is not prime
The number 1110 is not prime
The number 5683 is prime
p = 5683

p = generate_prime_number(10000, 100000)
print(f"p = {p}")

The number 69497 is prime
p = 69497

p = generate_prime_number(10000, 100000)
print(f"p = {p}")

The number 29375 is not prime
The number 36854 is not prime
The number 21716 is not prime
The number 96230 is not prime
The number 39050 is not prime
The number 90887 is prime
p = 90887

Another Method for generating prime numbers:

Another method for this uses the sympy library in Python. The sympy library provides a function called sympy.isprime that generates the nth prime number. We can use this function to generate prime numbers.

def generate_prime(start=100000, end=800000):
    while True:
        num = random.randint(start, end)
        if sp.isprime(num):
            return num

p = generate_prime(1000,10000)
print(f"p = {p}")

p = 8353

p = generate_prime(10000,1000000)
print(f"p = {p}")

p = 427369

p = generate_prime(2,20)
print(f"p = {p}")

p = 17

Generating a range of prime numbers:

Here is a slight modification that allows us to print all prime numbers in a given range. We can use the sympy.primerange function to generate all prime numbers in a given range.

def generate_primes_in_range(start=2, end=20):
    return list(sympy.primerange(start, end))

def print_range(start, end):
    primes = generate_primes_in_range(start, end)
    print(f"Primes in range {start} to {end} are: {primes}")

start = 1
end = 20
print_range(start, end)

Primes in range 1 to 20 are: [2, 3, 5, 7, 11, 13, 17, 19]

start = 1
end = 100
print_range(start, end)

Primes in range 1 to 100 are: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

start = 100
end = 300
print_range(start, end)

Primes in range 100 to 300 are: [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]

Fermat’s Little Theorem

Fermat’s Little Theorem states that if \(p\) is a prime number and \(a\) is an integer not divisible by \(p\), then:

\[ a^{p-1} \equiv 1 \mod p \]

This theorem is used in number theory and cryptography. It can be used to compute large powers modulo a prime number efficiently.

The steps to apply Fermat’s Little Theorem are as follows:

1. Ensure \(p\) is prime: Verify that \(p\) is a prime number.

2. Ensure \(a\) is not divisible by \(p\): Check that \(a\) is an integer not divisible by \(p\).

3. Apply the theorem: Compute \(a^{p-1} \mod p\).

For example, to compute \(3^{6} \mod 7\):

1. \(p = 7\) is prime.

2. \(a = 3\) is not divisible by 7.

3. Apply the theorem: \(3^{7-1} \equiv 1 \mod 7\)

4. \(3^{6} \mod 7 = 1\)

Therefore, \(3^{6} \equiv 1 \mod 7\).

def check_congruence(a, n):
    if pow(a, n-1, n) == 1 % n:
        print(f"true, {n} is congruent with base {a}.")
    else:
        print(f"false, {n} is not congruent with base {a}.")
        
def fermats_test(n, a):
    if pow(a, n-1, n) == 1:
        return True
    else:
        return False

%%time

n = 91
a = 3

check_congruence(a, n)

if fermats_test(n, a):
    print(f"{n} is probably prime.")
else:
    print(f"{n} is composite.")

true, 91 is congruent with base 3.
91 is probably prime.
CPU times: user 65 μs, sys: 14 μs, total: 79 μs
Wall time: 69.1 μs

Explanation

Testing if 91 is Prime with Base 3

Using Fermat’s Little Theorem: $\( 3^{90} \mod 91 \)$

Calculate \(3^{90} \mod 91\): $\( 3^{90} \equiv 1 \mod 91 \)$

Since the congruence holds true, 91 is probably prime.

Result:

• True, 91 is congruent with base 3.

• 91 is probably prime.

%%time

n = 88
a = 6

check_congruence(a,n)

if fermats_test(n, a):
    print(f"{n} is probably prime.")
else:
    print(f"{n} is composite.")

false, 88 is not congruent with base 6.
88 is composite.
CPU times: user 64 μs, sys: 13 μs, total: 77 μs
Wall time: 68.2 μs

Explanation

Testing if 88 is Prime with Base 6

Using Fermat’s Little Theorem: $\( 6^{87} \mod 88 \)$

Calculate \(6^{87} \mod 88\): $\( 6^{87} \not\equiv 1 \mod 88 \)$

Since the congruence does not hold true, 88 is composite.

Result:

• False, 88 is not congruent with base 6.

• 88 is composite.

%%time

n = 104729
a = 2

check_congruence(a,n)

if fermats_test(n, a):
    print(f"{n} is probably prime.")
else:
    print(f"{n} is composite.")

true, 104729 is congruent with base 2.
104729 is probably prime.
CPU times: user 76 μs, sys: 0 ns, total: 76 μs
Wall time: 68.9 μs

Explanation

Testing if 104729 is Prime with Base 2

Using Fermat’s Little Theorem: $\( 2^{104728} \mod 104729 \)$

Calculate \(2^{104728} \mod 104729\): $\( 2^{104728} \equiv 1 \mod 104729 \)$

Since the congruence holds true, 104729 is probably prime.

Result:

• True, 104729 is congruent with base 2.

• 104729 is probably prime.

Finding Coprimes

Two numbers \(a\) and \(b\) are said to be coprime (or relatively prime) if their greatest common divisor (gcd) is 1. This means they have no common prime factors.

The steps to determine if two numbers are coprime are as follows:

1. Find the prime factors: Determine the prime factors of both \(a\) and \(b\).

2. Check common factors: Check if there are any common prime factors.

3. Compute gcd: Use the Euclidean algorithm to find the gcd of \(a\) and \(b\). If \(\text{gcd}(a, b) = 1\), then \(a\) and \(b\) are coprime.

For example, to check if 14 and 15 are coprime:

1. Prime factors of 14: \(2, 7\)

2. Prime factors of 15: \(3, 5\)

3. No common prime factors.

4. \(\text{gcd}(14, 15) = 1\)

5. Therefore, 14 and 15 are coprime.

Finding the Coprime Pair

To find a coprime pair, we can generate two random numbers and check if they are coprime using the method described above. If the numbers are coprime it will output true, otherwise it will output false.

def are_coprime(p, q):
    if sp.gcd(p, q) == 1:
        return True
    else:
        return False

Checking \(44\) and \(10\) for coprimality:

p = 44
q = 10
are_coprime(p,q)

False

Explanation

Two numbers \(a\) and \(b\) are said to be coprime (or relatively prime) if their greatest common divisor (gcd) is 1. This means they have no common prime factors.

To determine if 44 and 10 are coprime, follow these steps:

1. Find the prime factors:

   • Prime factors of 44: \(2, 11\)

   • Prime factors of 10: \(2, 5\)

2. Check common factors:

   • Common prime factor: \(2\)

3. Compute gcd using the Euclidean Algorithm:

   • Apply the Euclidean algorithm to find \(\text{gcd}(44, 10)\): $\( \begin{aligned} 44 &= 10 \times 4 + 4 \\ 10 &= 4 \times 2 + 2 \\ 4 &= 2 \times 2 + 0 \end{aligned} \)$

   • The gcd is the last non-zero remainder: $\( \text{gcd}(44, 10) = 2 \)$

Since \(\text{gcd}(44, 10) \neq 1\), 44 and 10 are not coprime.

Checking \(12\) and \(25\) for coprimality:

p = 12
q = 25
are_coprime(p,q)

True

Explanation

Two numbers \(a\) and \(b\) are said to be coprime (or relatively prime) if their greatest common divisor (gcd) is 1. This means they have no common prime factors.

To determine if 12 and 25 are coprime, follow these steps:

1. Find the prime factors:

   • Prime factors of 12: \(2, 3\)

   • Prime factors of 25: \(5\)

2. Check common factors:

   • There are no common prime factors.

3. Compute gcd using the Euclidean Algorithm:

   • Apply the Euclidean algorithm to find \(\text{gcd}(12, 25)\): $\( \begin{aligned} 25 &= 12 \times 2 + 1 \\ 12 &= 1 \times 12 + 0 \end{aligned} \)$

   • The gcd is the last non-zero remainder: $\( \text{gcd}(12, 25) = 1 \)$

Since \(\text{gcd}(12, 25) = 1\), 12 and 25 are coprime.

Checking \(18\) and \(24\) for coprimality:

p = 18
q = 24
are_coprime(p,q)

False

Explanation

Two numbers \(a\) and \(b\) are said to be coprime (or relatively prime) if their greatest common divisor (gcd) is 1. This means they have no common prime factors.

To determine if 18 and 24 are coprime, follow these steps:

1. Find the prime factors:

   • Prime factors of 18: \(2, 3\)

   • Prime factors of 24: \(2, 3\)

2. Check common factors:

   • Common prime factors: \(2, 3\)

3. Compute gcd using the Euclidean Algorithm:

   • Apply the Euclidean algorithm to find \(\text{gcd}(18, 24)\): $\( \begin{aligned} 24 &= 18 \times 1 + 6 \\ 18 &= 6 \times 3 + 0 \end{aligned} \)$

   • The gcd is the last non-zero remainder: $\( \text{gcd}(18, 24) = 6 \)$

Since \(\text{gcd}(18, 24) \neq 1\), 18 and 24 are not coprime.

Listing the coprimes of a number

To list the coprimes of a number, we can use the following function. This function will list all the coprimes of a given number.

def list_coprimes(a, n):
    coprimes = []
    while len(coprimes) < n:
        b = random.randint(2, a - 1)
        if sp.gcd(a, b) == 1 and b not in coprimes:
            coprimes.append(b)
    return coprimes

Finding the coprimes of \(44\)

%%time

a = 44
n = 10
coprimes = find_coprimes(a, n)
print(f"{n} numbers coprime with {a} are: {coprimes}")

10 numbers coprime with 44 are: [19, 13, 43, 39, 29, 23, 21, 5, 25, 37]
CPU times: user 4.39 ms, sys: 68 μs, total: 4.46 ms
Wall time: 4.36 ms

Finding the coprimes of \(235319\)

%%time

a = 235319
n = 15
coprimes = find_coprimes(a, n)
print(f"{n} numbers coprime with {a} are: {coprimes}")

15 numbers coprime with 235319 are: [163414, 157744, 11463, 140811, 32392, 44937, 12774, 150809, 126921, 37073, 148998, 153702, 140029, 32500, 23621]
CPU times: user 2.74 ms, sys: 0 ns, total: 2.74 ms
Wall time: 2.74 ms

Finding the coprimes of \(80748256\)

%%time

a = 80748256
n = 20
coprimes = find_coprimes(a, n)
print(f"{n} numbers coprime with {a} are: {coprimes}")

20 numbers coprime with 80748256 are: [29114469, 58172365, 78108367, 62599371, 49755597, 61995723, 44851709, 70508381, 12524571, 42994715, 63593083, 70468773, 1072089, 37095855, 16820199, 1146747, 44594747, 61118371, 63942835, 54817271]
CPU times: user 5.17 ms, sys: 19 μs, total: 5.19 ms
Wall time: 5.08 ms

Prime Factorisation

Prime factorisation is the process of breaking down a composite number into a product of prime numbers. The steps are as follows:

1. Start with the smallest prime number: Begin with the smallest prime number, which is 2.

2. Divide the number: Divide the number by the prime number.

3. Check for divisibility: If the number is divisible by the prime number, record the prime factor and divide the number by this prime factor.

4. Repeat the process: Continue the process with the resulting quotient. If the quotient is no longer divisible by the current prime, move to the next larger prime number.

5. Continue until the quotient is 1: Repeat the steps until the quotient becomes 1. The prime factors are all the prime numbers recorded during the division process.

For a number \(n\), the prime factorization is:

\[ n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k} \]

where \(p_1, p_2, \ldots, p_k\) are prime numbers and \(e_1, e_2, \ldots, e_k\) are their respective exponents.

def find_factors(n):
    factors = []
    for i in range(1, n + 1):
        if n % i == 0:
            factors.append(i)
    print(f"Factors of {n} are: {factors}")
    
def find_prime_factors(n):
    factors = []
    for i in range(1, n + 1):
        if n % i == 0 and sympy.isprime(i):
            factors.append(i)
    print(f"Prime factors of {n} are: {factors}")
    

Example with the number \(12\)

n = 12
find_factors(n)
find_prime_factors(n)

Factors of 12 are: [1, 2, 3, 4, 6, 12]
Prime factors of 12 are: [2, 3]

Explanation

Factors of \(12\)

For \(12\):

• 1 divides 12: \(12 \div 1 = 12\)

• 2 divides 12: \(12 \div 2 = 6\)

• 3 divides 12: \(12 \div 3 = 4\)

• 4 divides 12: \(12 \div 4 = 3\)

• 6 divides 12: \(12 \div 6 = 2\)

• 12 divides 12: \(12 \div 12 = 1\)

The factors of \(12\) are:

\[ [1, 2, 3, 4, 6, 12] \]

Prime Factors of \(12\)

Prime factors are the prime numbers that multiply together to give the original number. To find the prime factors of \(12\), we start with the smallest prime number and divide \(12\) by prime numbers until we cannot divide further.

1. Divide by the smallest prime number \((2)\):

\[ 12 \div 2 = 6 \quad \text{(prime factor: 2)} \]

2. Continue dividing by \(2\):

\[ 6 \div 2 = 3 \quad \text{(prime factor: 2)} \]

3. \(3\) is a prime number:

\[ 3 \div 3 = 1 \quad \text{(prime factor: 3)} \]

The prime factors of \(12\) are:

\[ [2, 2, 3] \quad \text{or} \quad 2^2 \times 3 \]

Example with the number \(88\)

n = 88
find_factors(n)
find_prime_factors(n)

Factors of 88 are: [1, 2, 4, 8, 11, 22, 44, 88]
Prime factors of 88 are: [2, 11]

Explanation

Factors of \(88\)

For \(88\):

• 1 divides 88: \(88 \div 1 = 88\)

• 2 divides 88: \(88 \div 2 = 44\)

• 4 divides 88: \(88 \div 4 = 22\)

• 8 divides 88: \(88 \div 8 = 11\)

• 11 divides 88: \(88 \div 11 = 8\)

• 22 divides 88: \(88 \div 22 = 4\)

• 44 divides 88: \(88 \div 44 = 2\)

• 88 divides 88: \(88 \div 88 = 1\)

The factors of \(88\) are:

\[ [1, 2, 4, 8, 11, 22, 44, 88] \]

Prime Factors of \(88\)

Prime factors are the prime numbers that multiply together to give the original number. To find the prime factors of \(88\), we start with the smallest prime number and divide \(88\) by prime numbers until we cannot divide further.

1. Divide by the smallest prime number \((2)\):

\[ 88 \div 2 = 44 \quad \text{(prime factor: 2)} \]

2. Continue dividing by \(2\):

\[ 44 \div 2 = 22 \quad \text{(prime factor: 2)} \]

3. Continue dividing by \(2\):

\[ 22 \div 2 = 11 \quad \text{(prime factor: 2)} \]

4. \(11\) is a prime number:

\[ 11 \div 11 = 1 \quad \text{(prime factor: 11)} \]

The prime factors of \(88\) are:

\[ [2, 2, 2, 11] \quad \text{or} \quad 2^3 \times 11 \]

Example with the number \(138\)

n = 138
find_factors(n)
find_prime_factors(n)

Factors of 138 are: [1, 2, 3, 6, 23, 46, 69, 138]
Prime factors of 138 are: [2, 3, 23]

Explanation

Factors of \(138\)

For \(138\):

• 1 divides 138: \(138 \div 1 = 138\)

• 2 divides 138: \(138 \div 2 = 69\)

• 3 divides 138: \(138 \div 3 = 46\)

• 6 divides 138: \(138 \div 6 = 23\)

• 23 divides 138: \(138 \div 23 = 6\)

• 46 divides 138: \(138 \div 46 = 3\)

• 69 divides 138: \(138 \div 69 = 2\)

• 138 divides 138: \(138 \div 138 = 1\)

The factors of \(138\) are:

\[ [1, 2, 3, 6, 23, 46, 69, 138] \]

Prime Factors of \(138\)

Prime factors are the prime numbers that multiply together to give the original number. To find the prime factors of \(138\), we start with the smallest prime number and divide \(138\) by prime numbers until we cannot divide further.

1. Divide by the smallest prime number \((2)\):

\[ 138 \div 2 = 69 \quad \text{(prime factor: 2)} \]

2. Move to the next prime number \((3)\):

\[ 69 \div 3 = 23 \quad \text{(prime factor: 3)} \]

3. \(23\) is a prime number:

\[ 23 \div 23 = 1 \quad \text{(prime factor: 23)} \]

The prime factors of \(138\) are: $\( [2, 3, 23] \)$

Example with randomly generating a number

n = random.randint(100, 1000)
find_factors(n)
find_prime_factors(n)

Factors of 750 are: [1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 125, 150, 250, 375, 750]
Prime factors of 750 are: [2, 3, 5]

n = random.randint(1000, 10000)
find_factors(n)
find_prime_factors(n)

Factors of 3820 are: [1, 2, 4, 5, 10, 20, 191, 382, 764, 955, 1910, 3820]
Prime factors of 3820 are: [2, 5, 191]

n = random.randint(10000, 100000)
find_factors(n)
find_prime_factors(n)

Factors of 32130 are: [1, 2, 3, 5, 6, 7, 9, 10, 14, 15, 17, 18, 21, 27, 30, 34, 35, 42, 45, 51, 54, 63, 70, 85, 90, 102, 105, 119, 126, 135, 153, 170, 189, 210, 238, 255, 270, 306, 315, 357, 378, 459, 510, 595, 630, 714, 765, 918, 945, 1071, 1190, 1530, 1785, 1890, 2142, 2295, 3213, 3570, 4590, 5355, 6426, 10710, 16065, 32130]
Prime factors of 32130 are: [2, 3, 5, 7, 17]

GCD and LCM

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The Least Common Multiple (LCM) of two numbers is the smallest positive integer that is divisible by both numbers.

Finding the GCD

To find the GCD of two numbers \(a\) and \(b\), we can use the Euclidean Algorithm:

1. Divide \(a\) by \(b\): Compute the quotient and remainder.

2. Replace \(a\) with \(b\) and \(b\) with the remainder: Repeat the process until the remainder is 0.

3. GCD is the last non-zero remainder.

Finding the LCM

To find the LCM of two numbers \(a\) and \(b\), we can use the relationship between GCD and LCM:

\[ \text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)} \]

def find_gcd_lcm(a, b):
    gcd = sp.gcd(a, b)
    lcm = a * b // gcd
    print(f"GCD of {a} and {b} is {gcd}")
    print(f"LCM of {a} and {b} is {lcm}")

Finding the GCD and LCM of \(44\) and \(12\)

a = 44
b = 12

find_gcd_lcm(a, b)

GCD of 44 and 12 is 4
LCM of 44 and 12 is 132

Explanation

To find the GCD of \(44\) and \(12\), we can use the Euclidean Algorithm:

1. Divide \(44\) by \(12\):

\[ 44 = 12 \times 3 + 8 \]

2. Replace \(44\) with \(12\) and \(12\) with \(8\):

\[ 12 = 8 \times 1 + 4 \]

3. Replace \(12\) with \(8\) and \(8\) with \(4\):

\[ 8 = 4 \times 2 + 0 \]

4. The GCD is the last non-zero remainder:

\[ \text{GCD}(44, 12) = 4 \]

Finding the LCM

To find the LCM of \(44\) and \(12\), use the relationship between GCD and LCM:

\[ \text{LCM}(44, 12) = \frac{|44 \times 12|}{\text{GCD}(44, 12)} = \frac{528}{4} = 132 \]

Finding the GCD and LCM of \(15\) and \(25\)

a = 15
b = 25

find_gcd_lcm(a, b)

GCD of 15 and 25 is 5
LCM of 15 and 25 is 75

Explanation

To find the GCD of \(15\) and \(25\), we can use the Euclidean Algorithm:

1. Divide \(25\) by \(15\):

\[ 25 = 15 \times 1 + 10 \]

2. Replace \(25\) with \(15\) and \(15\) with \(10\):

\[ 15 = 10 \times 1 + 5 \]

3. Replace \(15\) with \(10\) and \(10\) with \(5\):

\[ 10 = 5 \times 2 + 0 \]

4. The GCD is the last non-zero remainder:

\[ \text{GCD}(15, 25) = 5 \]

Finding the LCM

To find the LCM of \(15\) and \(25\), use the relationship between GCD and LCM:

\[ \text{LCM}(15, 25) = \frac{|15 \times 25|}{\text{GCD}(15, 25)} = \frac{375}{5} = 75 \]

Finding the GCD and LCM of \(30\) and \(45\)

a = 30
b = 45

find_gcd_lcm(a, b)

Explanation

To find the GCD of \(30\) and \(45\), we can use the Euclidean Algorithm:

1. Divide \(45\) by \(30\):

\[ 45 = 30 \times 1 + 15 \]

2. Replace \(45\) with \(30\) and \(30\) with \(15\):

\[ 30 = 15 \times 2 + 0 \]

3. The GCD is the last non-zero remainder:

\[ \text{GCD}(30, 45) = 15 \]

Finding the LCM

To find the LCM of \(30\) and \(45\), use the relationship between GCD and LCM:

\[ \text{LCM}(30, 45) = \frac{|30 \times 45|}{\text{GCD}(30, 45)} = \frac{1350}{15} = 90 \]

Finding the GCD and LCM of \(21\) and \(14\)

a = 21
b = 14

find_gcd_lcm(a, b)

Explanation

To find the GCD of \(21\) and \(14\), we can use the Euclidean Algorithm:

1. Divide \(21\) by \(14\):

\[ 21 = 14 \times 1 + 7 \]

2. Replace \(21\) with \(14\) and \(14\) with \(7\):

\[ 14 = 7 \times 2 + 0 \]

3. The GCD is the last non-zero remainder:

\[ \text{GCD}(21, 14) = 7 \]

Finding the LCM

To find the LCM of \(21\) and \(14\), use the relationship between GCD and LCM:

\[ \text{LCM}(21, 14) = \frac{|21 \times 14|}{\text{GCD}(21, 14)} = \frac{294}{7} = 42 \]