Common Factor Calculator

Definition and Properties

A common factor (or common divisor) of two or more integers is an integer that divides each of them without leaving a remainder. The set of common factors has several important properties: it is closed under division, contains 1 (the trivial factor), and has a maximum element called the Greatest Common Divisor (GCD).

\textCF(a_1, a_2, \ldots, a_n) = \d \in \mathbbZ^+ : d \mid a_i \text for all i = 1, 2, \ldots, n\

Finding Common Factors Algorithm

To find all common factors of multiple numbers: 1) Factor each number into its prime components, 2) Identify the intersection of all factor sets, 3) The GCD is the product of the minimum power of each common prime factor.

\textIf a = p_1^α_1 p_2^α_2 ·s p_k^α_k \text and b = p_1^β_1 p_2^β_2 ·s p_k^β_k, \text then \gcd(a,b) = p_1^\min(α_1,β_1) p_2^\min(α_2,β_2) ·s p_k^\min(α_k,β_k)

Greatest Common Divisor (GCD)

The GCD of two or more integers is the largest positive integer that divides each of them without remainder. It represents the maximum common factor and has applications in fraction simplification, modular arithmetic, and linear Diophantine equations.

\gcd(a_1, a_2, \ldots, a_n) = \max\d \in \mathbbZ^+ : d \mid a_i \text for all i\

Euclidean Algorithm

The Euclidean algorithm is an efficient method to compute GCD. It relies on the property that gcd(a,b) = gcd(b, a mod b). This algorithm has O(log(min(a,b))) time complexity and forms the foundation for extended Euclidean algorithm used in modular inverses.

\gcd(a, b) = \gcd(b, a \bmod b) \text with base case \gcd(a, 0) = a

Extended Euclidean Algorithm

The extended version finds integers x and y such that ax + by = gcd(a,b). This is crucial for solving linear Diophantine equations and finding modular multiplicative inverses.

\gcd(a, b) = ax + by \text where x, y \in \mathbbZ

Fundamental Theorem of Arithmetic

Every positive integer greater than 1 can be uniquely represented as a product of prime powers. This uniqueness is essential for factor analysis and forms the theoretical foundation for many number-theoretic algorithms.

n = p_1^α_1 p_2^α_2 ·s p_k^α_k \text where p_i \text are distinct primes

Properties of GCD

Key properties: 1) gcd(a,b) = gcd(b,a) (commutative), 2) gcd(gcd(a,b),c) = gcd(a,gcd(b,c)) (associative), 3) gcd(ka,kb) = k·gcd(a,b) (distributive over multiplication), 4) If gcd(a,b) = 1, then a and b are coprime.

\gcd(ka, kb) = k · \gcd(a, b) \text and \gcd(\gcd(a,b), c) = \gcd(a, \gcd(b,c))

Applications in Number Theory

Common factors appear in: fraction simplification, solving linear Diophantine equations, Chinese Remainder Theorem, RSA cryptography, and modular arithmetic. They are fundamental to understanding divisibility relationships.

(a)/(b) = (a/\gcd(a,b))/(b/\gcd(a,b)) \text (simplified fraction)

Prime Factorization GCD Formula

When numbers are expressed in their prime factorization, the GCD can be found by taking the minimum power of each common prime factor. This method is particularly useful for large numbers.

\textIf a_i = \prod_j=1^k p_j^α_ij, \text then \gcd(a_1, \ldots, a_n) = \prod_j=1^k p_j^\min_i(α_ij)

Extended Euclidean Algorithm

The extended version finds integers x and y such that ax + by = gcd(a,b). This is crucial for solving linear Diophantine equations and finding modular multiplicative inverses in cryptography.

\gcd(a, b) = ax + by \text where x, y \in \mathbbZ

Factor Count Formula

The number of factors of a positive integer can be determined from its prime factorization using the tau function. This is useful for analyzing the structure of factor sets.

\textIf n = \prod_i=1^k p_i^α_i, \text then \tau(n) = \prod_i=1^k (α_i + 1)

LCM-GCD Relationship

There is a fundamental relationship between the Least Common Multiple and Greatest Common Divisor. This identity is essential for many number-theoretic applications.

\textlcm(a, b) = (a × b)/(\gcd(a, b))

Bézout's Identity

Bézout's identity states that the GCD of two integers can be expressed as a linear combination of those integers. This is fundamental to the extended Euclidean algorithm and has applications in cryptography.

\gcd(a, b) = \min\ax + by : ax + by > 0, x, y \in \mathbbZ\

Divisibility Notation and Properties

The mathematical notation a|b means "a divides b" or "a is a divisor of b". This notation is fundamental to understanding factor relationships and divisibility rules.

a \mid b \Leftrightarrow \exists k \in \mathbbZ : b = ak

Prime Factorization Formula

Every positive integer greater than 1 can be uniquely expressed as a product of prime powers. This factorization is essential for finding GCD and understanding number structure.

n = p_1^α_1 p_2^α_2 ·s p_k^α_k \text where p_i \text are distinct primes

Factor Count (Tau Function)

The tau function τ(n) counts the total number of positive divisors of n. It can be calculated directly from the prime factorization.

\tau(n) = \prod_i=1^k (α_i + 1)

Chinese Remainder Theorem

When solving systems of congruences with coprime moduli, the Chinese Remainder Theorem provides a unique solution. This theorem relies heavily on GCD properties.

\begincases x \equiv a_1 ±odm_1 \\ x \equiv a_2 ±odm_2 \endcases \text has unique solution when \gcd(m_1, m_2) = 1

Modular Arithmetic and Inverses

Finding modular multiplicative inverses is crucial in cryptography and number theory. The extended Euclidean algorithm provides an efficient method.

a^-1 \equiv x ±odm \text where ax \equiv 1 ±odm \text and \gcd(a, m) = 1

Worked Example

Inputs

• numbers: 12, 18, 24

Result: 1, 2, 3, 6

Explanation

**Step-by-Step Solution:**

**Step 1: Find factors of each number** - Factors of 12: 1, 2, 3, 4, 6, 12 - Factors of 18: 1, 2, 3, 6, 9, 18 - Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24

**Step 2: Identify common factors** Looking for numbers that appear in all three lists: - 1 appears in all lists ✓ - 2 appears in all lists ✓ - 3 appears in all lists ✓ - 4 appears only in 12 and 24 ✗ - 6 appears in all lists ✓ - 8, 9, 12, 18, 24 don't appear in all lists ✗

**Step 3: Determine GCD** The greatest common divisor is the largest common factor: **6**

**Step 4: Verification** - 12 ÷ 6 = 2 ✓ - 18 ÷ 6 = 3 ✓ - 24 ÷ 6 = 4 ✓

**Prime Factorization Method:** - 12 = 2² × 3¹ - 18 = 2¹ × 3² - 24 = 2³ × 3¹

GCD = 2^min(2,1,3) × 3^min(1,2,1) = 2¹ × 3¹ = 6

**Applications:** - Simplifying fractions: 12/18 = (12÷6)/(18÷6) = 2/3 - Finding least common multiple: LCM(12,18,24) = (12×18×24)÷6 = 72

Prime Numbers Example

Inputs

• numbers: 7, 11, 13

Result: 1

Explanation

**Prime Numbers Have Only 1 as Common Factor**

Prime numbers (7, 11, 13) have only two factors each: 1 and themselves. - Factors of 7: 1, 7 - Factors of 11: 1, 11 - Factors of 13: 1, 13

Since 1 is the only factor common to all three numbers, GCD(7, 11, 13) = 1.

**Mathematical Insight:** When numbers are coprime (have GCD = 1), they share no common prime factors.