3.2: Prime Factorization – Number Theory

3.2 Prime Factorization



Jump to:


TODO: Introduction


Definition: Prime, Composite

We say an integer $n > 1$ is prime if its only factors are 1 and $n$. If $n$ has factors other than 1 and itself, then we say it is composite. The number 1 is neither prime nor composite.


This should be nothing new. However, what may be new is the process of checking to see if a number is prime. Of course, to see if some $n$ is prime, we could test to see if any of $2, 3, … n-2, n-1$ divide it. However, we don’t need to check any even number greater than 2, since if any other even number divides $n$, then so will 2. We can still throw away many potential factors, though – see if you can notice a pattern below:

$$