3.3.3 Bad assumption!

As it turns out, most programming languages do not have a method to find a prime factor $f$ of a given integer $n$ . Oh, well. That means we need to specify an algorithm just to do this. Again, it is best to try to do this by hand first.

Let us assume $n=15$ , and we are to find a prime factor of it.

Although not necessarily the most efficient method, one way is to try out all integer greater than or equal to 2 until we find one that is a factor. This requires the explanation of the ``mod'' operator. $a \mod b$ is the remainder of $\frac{a}{b}$ . In other words, $10 \mod 3 = 1$ , $23 \mod 10 = 3$ and etc.

Given this operator, we can now explain how we can find a prime factor of 15:

• $15 \mod 2 = 1$ , therefore 2 is not a factor of 15
• $15 \mod 3 = 0$ , therefore 3 is a factor of 15!