posted by Anonymous on .
I need some help with this problem. When finding the factors of 841, what is the largest factor you would have to test? What theorem supports this? Can someone please help me with this? Thanks.
Denote your number by N. Suppose N is divisible by M. So, we have:
N = M Y
where Y is another integer. Then, M is also divisible by Y. If we are testing different numbers starting from small to large, then it is not possible for Y to be smaller than M, because then you should have encountered the divisor Y already.
This means that you don't have to test numbers M for which
N/M < M ------->
M^2 > N --------->
M > sqrt(N)
So, we only need to test numbers smaller than or equal to the square root of N.