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.
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.