[Math] Factlets about integer factorization

There is a toyish *NIX utility factor available, which can factorize small numbers.

GCD is simply common factors. Here is 3*3:

% factor
9999999999
9999999999: 3 3 11 41 271 9091
87654321
87654321: 3 3 1997 4877

Let's check:

% python3
Python 3.8.10 (default, Jun 22 2022, 20:18:18)
[GCC 9.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> math.gcd(9999999999, 87654321)
9
>>>

Obviously, prime numbers have no factors:

% factor
409993
409993: 409993

Hence, any number smaller than a prime will be coprime with it, because they don't share common factors. (But larger number can share.) GCD=1 for coprime numbers.

>>> math.gcd(409993, 10)
1
>>> math.gcd(409993, 100)
1
>>> math.gcd(409993, 123)
1
>>> math.gcd(409993, 999)
1

If you know common factors of x and y, you can do x/y division operation faster by dropping these common factors.

% factor
999999999
999999999: 3 3 3 3 37 333667
87654321
87654321: 3 3 1997 4877

Remove "3 3" from both lists of factors.

% bc
bc 1.07.1
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006, 2008, 2012-2017 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.

scale=5

999999999/87654321
11.40845

3*3*37*333667
111111111

1997*4877
9739369

111111111/9739369
11.40845

(3*3*37*333667)/(1997*4877)
11.40845

Division of smaller numbers is faster, of course.

(the post first published at 20220724.)


List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.