Concise way to accurately find factors of any number?

95 Views Asked by At

The last number of $365$ is $5$, therefore I’ve been told that $5$ is a factor of $365$, which it clearly is. This however does not work for other numbers, i.e., $9$ is not a factor of $8599$.

I’ve also been told to consider the sum of the numbers, i.e., $315: 3+1+5 = 9$, and since $9$ is divisible by $3$, $3$ is a factor of $315$, which it is. But this is severely limited because it only holds if the sum is a multiple of $3$, so using this for $389$ doesn’t work because $3+8+9 = 20$, which isn’t a multiple of $3$.

With this info in mind, is there a reliable way to factor numbers using inherent properties? If there is not, I am a bit worried that I will be unable to reliably factor any given number of a reasonable size. Thank you.

1

There are 1 best solutions below

0
On

As noted in the comments, you can find plenty of similar divisibility rules in this Wikipeida article.

With this info in mind, is there a reliable way to factor numbers using inherent properties? If there is not, I am a bit worried that I will be unable to reliably factor any given number of a reasonable size.

You are right to be worried, since factoring numbers is a hard problem. This is especially true for large integers with a small number of large prime factors. A good example are semiprimes, i.e., large integers $n=p_1\times p_2$ with exactly two very large prime components $p_1$ and $p_2$.

In fact, integer factorization is so hard, modern cryptographic methods rely on them.