Finding Coprimes

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.

Hide code cell source 
import sympy as sp
from sympy import *
from math import gcd
import random

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

Examples:#

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{split} \begin{aligned} 44 &= 10 \times 4 + 4 \\ 10 &= 4 \times 2 + 2 \\ 4 &= 2 \times 2 + 0 \end{aligned} \end{split}\]

    • 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{split} \begin{aligned} 25 &= 12 \times 2 + 1 \\ 12 &= 1 \times 12 + 0 \end{aligned} \end{split}\]

    • 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{split} \begin{aligned} 24 &= 18 \times 1 + 6 \\ 18 &= 6 \times 3 + 0 \end{aligned} \end{split}\]

    • 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
Contents