Connecting Periodic Functions and Factoring

To answer Cardy’s question, we will look at the general connection between finding the period of a function and factoring a number. At least for me, if someone had told me there is such a connection, I would have been highly skeptical. The concepts seem like they have no relationship. But number theory has many surprises of that sort.

Note: If you are willing to accept that connection, feel free to skip ahead to the next lesson.

To see how the connection comes about, we again assume $N = pq$ and follow the algorithm’s steps to find $p$ and $q.$ The first step seems totally unmotivated: We choose an integer $a < N$ and check to see that a is not a factor of $N$; that is, $N$ is not evenly divisible by $a$. If it is divisible by $a$, we have found a factor and we are essentially finished. So, we assume that a is not a factor of $N$.