§ Why searching for divisors upto
- It's not that all divisors are smaller than . For example, consider . , but one of its diviors ( ) is greater than 4.
- Rather, it is that if there is a divisor (for large) which is larger than , there will be another divisor which is smaller than .
- Proof: Suppose , . So there exists an such that , or .
- Since , . Thus .
- So if we wish to find some factor of , we can simply search within the range .
- If has no factors in the range , then must be prime, for if did have a larger factor, would also have a smaller factor we would have found.