Theoretical Principles & Computational Physics Guide
Integer Factorization: Divisor Identification & Prime Decomposition
Dr. Alorika Chatterjee & Dr. Anirban Shaw
Science & Physics Learners
Python 3 / NumPy / SciPy
1. Core Principles & Theoretical Framework
Canonical Decomposition: Every integer $N > 1$ factors uniquely into a product of prime powers: $N = \prod p_i^{\alpha_i}$.
Divisor Pairs: Factors appear in symmetrical pairs $(d, N/d)$. Finding one immediately yields the conjugate factor.
Resonance & Symmetry: Factorization determines commensurability in coupled oscillator modes and crystallographic unit cell subdivisions.
2. Mathematical Formulation & Algorithmic Pipeline
Fundamental Theorem of Arithmetic:
$$ N = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \quad \text{Number of Divisors: } d(N) = \prod_{i=1}^k (\alpha_i + 1) $$
3. Numerical Mechanics & Implementation Logic
- Trial Factorization: Test potential divisor $d = 2$. While $N \pmod d == 0$, record $d$ and replace $N \leftarrow N / d$.
- Odd Factors: Increment $d$ by 2 (checking $3, 5, 7, \dots$) up to $\lfloor\sqrt{N}\rfloor$.
- Prime Remainder: If $N > 1$ after loop, the remaining $N$ is itself the final prime factor.
4. Relevant Computational Practice Exercises
Exercise 1
Write a script that takes an integer $N$ and prints its full prime factorization in standard power format (e.g. $360 = 2^3 \times 3^2 \times 5^1$).
Exercise 2
Find all proper divisors of $N = 28$ and verify whether it is a mathematically perfect number (sum of divisors equals $N$).
Exercise 3
Compute the greatest common divisor $\gcd(a, b)$ of two large numbers using the Euclidean algorithm.
- G. H. Hardy and E. M. Wright, "An Introduction to the Theory of Numbers", Oxford (2008).