Prime Toolkit

Definitions & Why 1 is Special

A prime number is an integer $p > 1$ that has exactly two distinct positive divisors: $1$ and itself. An integer $n > 1$ that is not prime is composite. The integer $1$ is defined as a unit. If $1$ were considered prime, the Fundamental Theorem of Arithmetic (which states every integer $>1$ has a unique prime factorization) would fail, as we could write $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1^2 \cdot 2 \cdot 3$, violating uniqueness.

$\sqrt{n}$ Compositeness Theorem Proof Sketch

Since $n$ is composite, there exist integers $a, b > 1$ such that $n = a \cdot b$. If both $a > \sqrt{n}$ and $b > \sqrt{n}$, then $a \cdot b > \sqrt{n} \cdot \sqrt{n} = n$, yielding a contradiction ($n > n$). Thus, at least one factor must be $\le \sqrt{n}$. Every integer $>1$ has a prime factor, so there must be a prime $p \le \sqrt{n}$ dividing $n$.

Algorithms & Complexity

Trial Division: Checks if $n$ is divisible by $2$ or any odd integer $d \in [3, \lfloor\sqrt{n}\rfloor]$. Its time complexity is $\mathcal{O}(\sqrt{n})$, making it extremely fast for $n \le 10^{12}$ but impractically slow for cryptographic sizes (e.g. $10^{300}$).

Sieve of Eratosthenes: Systematically identifies primes up to $N$ by marking multiples of each discovered prime starting from $2$. Its time complexity is $\mathcal{O}(N \log \log N)$. MechForge optimally caches queries up to $17,000,000$ (internal limit) in milliseconds using typed arrays.

Certificates vs. Probabilistic Proofs

The factorization produced here is a deterministic certificate — it explicitly provides the witnesses (the exact divisors) that can be verified by independent multiplication in constant time. In contrast, modern cryptographic primality testing uses probabilistic methods like the Miller-Rabin test, which guarantees primality to an arbitrarily high degree of confidence but does not produce explicit factors.

Limits & Failure Modes

Integers exceeding the IEEE-754 double-precision safe integer limit ($2^{53}-1 \approx 9 \times 10^{15}$) cannot be represented exactly in standard floating-point hardware. Entering such values silently truncates low-order bits, leading to false composite/primality outputs. This tool strictly rejects inputs beyond $10^{12}$ to guarantee rigorous exactness without needing arbitrary-precision (BigInt) libraries.

Hunting-Tooth Gear Pair Contact Cycles

In mechanical transmission design, choosing relatively prime tooth counts for mating gears (e.g., a $17$-tooth pinion and $43$-tooth gear) creates a "hunting tooth" configuration. Because the tooth counts share no common divisors ($\gcd(17,43)=1$), a specific tooth on the pinion will contact every single tooth on the bull gear before hitting the same tooth again. This distributes wear evenly across all gear faces over multiple revolutions.

GCD/LCM Repeat Periods & Sampling

When placing sampling sensors or scheduling maintenance for systems with multiple periodic events, prime intervals prevent early synchronization. The combined repeat period of two periodic events with lengths $A$ and $B$ is their Lowest Common Multiple ($\text{LCM}$). If $A$ and $B$ are relatively prime, the $\text{LCM}$ is simply $A \times B$, pushing the overlapping synchronization event to the maximum possible interval.

Indexing Ratio Factorability

Dividing a circular workpiece into prime-numbered segments requires compound or differential indexing heads. For example, cutting a 127-tooth gear cannot be done with standard gear trains because 127 is prime and cannot be factored into smaller gear ratios. Understanding the explicit prime factorization of a transmission ratio dictates the required gearing setup for the indexing table.