Often in problems I find myself having a hard time factoring really large or "complex" numbers.
How am I supposed to know that $43,911$ is $41 * 63 *17$ ?
Are there any methods or tricks or ways we can approximate closer to the answer instead of a simple Trial-and-Error?
How exactly does one go about finding Prime or Integer Factors of any given number with no access to a calculator or a help table?
On
Ever composite number has a prime factor less than or equal to its square root. Proof: Suppose some two factors are both greater than the square root. Then the product must be greater than the original number, a contradiction. This proves there is a factor less than or equal to the square root. Any factor is either prime or has a prime factor. Thus there exists a prime factor.
This means if you do trial and error, you only have to test $\approx 2\sqrt{x}/\ln x$ prime numbers.
Consider 911. $\sqrt{911}\approx 30. $ Prime under 30 are $2,3,5,7,11,13,17,19,23,29$.
911 is not even so it isn't divisible by 2. The sum of its digits is 11, so it isn't divisible by 3. It doesn't end in 5 or 0 so it isn't divisible by 5.
$911=700+210+1$, so it leaves a remainder of 1 when divided by 7, so it isn't divisble by seven. Alternatively if we express 911 as $10A+B$ where B is the ones digit and A is [911-(ones digit)]/10, then $911/7$ has the same remainder as $(3A+B)/7$. There are divisibility rules along these lines for many of the smaller prime numbers.
$9-1+1=9$, so 911 is not divisible by 11. It would have to be 0 to be divisible by 11.
$911=880+31=(39+1)22+31\equiv 1 \pmod{13}$. In other words, to test if a number is divisibly by 13, divide the number by 40 then add the quotient to the remainder. IF this new number is divisible by 13, then so is the original. Thus 911 is not divisible by 13.
$911=(5\cdot 17+15)\cdot 9 + 10\cdot 1+ 1\equiv 9\pmod{17}$, so its not divisible by 17.
$911=(20)\cdot 5 \cdot 9+11 \equiv 5 \pmod{19}$
$911=(45\cdot 20)+11\equiv -135+11\equiv 6(20)+4\equiv 9 \pmod{23}$
$911=30\cdot 30+11\equiv 12 \pmod{29}$ hence 911 is not divisible by 29.
It follows 911 is prime.
This gives you tips on by hand primality testing. For 43,911, similar principles apply, but you'll be testing divisibility by 40 multi digit primes.
There are certainly better methods than trial division, but not much better. If you were writing a computer program which factored numbers, you’d still use trial division for many of the smaller numbers, and then other more complicated methods for much larger numbers. There’s techniques related to elliptic curves I believe, but that’s besides the point.
Factoring is an NP problem, which means that it’s not known if there is a “polynomial time” algorithm for doing it. Essentially, factoring seems really difficult because, in a very precise way, it is really difficult.
If you find yourself needing to factor numbers a lot, you can write a program which implements a variation of the Sieve of Eratosthenes which factors every number up to a given number fairly quickly. And then you can just store that table somewhere convenient.