The Greatest Common Divisor<\/strong> (also called Greatest Common Factor or Highest Common Factor) of two or more integers is the largest positive integer<\/strong> that divides all of them without leaving a remainder<\/strong>.<\/p>\n Examples:<\/p>\n Important timeline:<\/p>\n Today (2025) almost everyone is on 1.20+ or 2.x, so we can use the modern functions.<\/p>\n Element-wise on arrays<\/strong> (very powerful)<\/p>\n This is the most common real need.<\/p>\n Along an axis<\/strong> (very useful with 2D data)<\/p>\n Example 1 \u2013 Finding when multiple periodic events align again<\/strong><\/p>\n Example 2 \u2013 Simplifying fractions (classic school problem)<\/strong><\/p>\n Example 3 \u2013 Finding GCD of array elements along axis<\/strong><\/p>\n Example 4 \u2013 Batch GCD computation (very common in coding problems)<\/strong><\/p>\n Golden rule #1<\/strong> If your NumPy is 1.18 or newer \u2192 always use np.gcd and np.gcd.reduce<\/strong> \u2014 they are optimized and clean.<\/p>\n Golden rule #2<\/strong> When you want GCD of more than two numbers, always use .reduce()<\/strong> \u2014 never write a loop.<\/p>\n Golden rule #3<\/strong> GCD is always positive<\/strong> \u2014 NumPy returns positive values even if inputs are negative.<\/p>\n Golden rule #4<\/strong> GCD(a, 0) = |a|<\/strong> GCD(0, 0) = 0<\/strong> (by convention)<\/p>\n Golden rule #5<\/strong> LCM and GCD are closely related:<\/p>\n So if you have np.gcd, you can easily build LCM yourself.<\/p>\n Would you like to continue with any of these next?<\/p>\n Just tell me what you want to focus on next! \ud83d\ude0a<\/p>\n","protected":false},"excerpt":{"rendered":" 1. What is GCD? (quick but important reminder) The Greatest Common Divisor (also called Greatest Common Factor or Highest Common Factor) of two or more integers is the largest positive integer that divides all...<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[75],"tags":[],"class_list":["post-2551","post","type-post","status-publish","format-standard","hentry","category-numpy"],"_links":{"self":[{"href":"https:\/\/demo.materiamedica.net\/demo6\/wp-json\/wp\/v2\/posts\/2551","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demo.materiamedica.net\/demo6\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demo.materiamedica.net\/demo6\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demo.materiamedica.net\/demo6\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demo.materiamedica.net\/demo6\/wp-json\/wp\/v2\/comments?post=2551"}],"version-history":[{"count":1,"href":"https:\/\/demo.materiamedica.net\/demo6\/wp-json\/wp\/v2\/posts\/2551\/revisions"}],"predecessor-version":[{"id":2552,"href":"https:\/\/demo.materiamedica.net\/demo6\/wp-json\/wp\/v2\/posts\/2551\/revisions\/2552"}],"wp:attachment":[{"href":"https:\/\/demo.materiamedica.net\/demo6\/wp-json\/wp\/v2\/media?parent=2551"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demo.materiamedica.net\/demo6\/wp-json\/wp\/v2\/categories?post=2551"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demo.materiamedica.net\/demo6\/wp-json\/wp\/v2\/tags?post=2551"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n
2. NumPy has built-in GCD support \u2013 since when?<\/h3>\n
\n\n
\n \nVersion<\/th>\n Has np.gcd?<\/th>\n Has np.gcd.reduce?<\/th>\n Recommendation<\/th>\n<\/tr>\n<\/thead>\n \n < 1.9<\/td>\n No<\/td>\n No<\/td>\n You must implement it<\/td>\n<\/tr>\n \n 1.9 \u2013 1.17<\/td>\n Yes<\/td>\n No<\/td>\n Use np.gcd for pairs<\/td>\n<\/tr>\n \n \u2265 1.18<\/td>\n Yes<\/td>\n Yes<\/td>\n Use np.gcd and np.gcd.reduce<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n 3. The two main GCD functions you need<\/h3>\n
\n\n
\n \nFunction<\/th>\n What it does<\/th>\n Returns<\/th>\n Typical usage<\/th>\n<\/tr>\n<\/thead>\n \n np.gcd(a, b)<\/td>\n Element-wise GCD of two arrays (or scalars)<\/td>\n array or scalar<\/td>\n pairwise GCD<\/td>\n<\/tr>\n \n np.gcd.reduce(arr)<\/td>\n GCD of all elements in array (or along axis)<\/td>\n scalar or reduced array<\/td>\n GCD of many numbers<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n 4. Basic usage examples \u2013 scalars and pairs<\/h3>\n
print(\"GCD of 12 and 18:\", np.gcd(12, 18)) # 6\r\nprint(\"GCD of 48 and 60:\", np.gcd(48, 60)) # 12\r\nprint(\"GCD of 7 and 13:\", np.gcd(7, 13)) # 1\r\nprint(\"GCD of 0 and 25:\", np.gcd(0, 25)) # 25\r\nprint(\"GCD of 0 and 0:\", np.gcd(0, 0)) # 0<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\na = np.array([12, 48, 7, 0, 30])\r\nb = np.array([18, 60, 13, 25, 42])\r\n\r\nprint(\"Pairwise GCD:\", np.gcd(a, b))\r\n# [ 6 12 1 25 6]<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n5. Finding GCD of many numbers \u2013 np.gcd.reduce<\/h3>\n
numbers = np.array([12, 18, 24, 36, 48])\r\n\r\nprint(\"GCD of all:\", np.gcd.reduce(numbers)) # 6\r\n\r\n# More realistic example\r\nperiods = np.array([12, 18, 30, 45, 60])\r\nprint(\"When do all cycles repeat together?\", np.gcd.reduce(periods)) # 6<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\nmatrix = np.array([\r\n [12, 18, 24],\r\n [30, 45, 60],\r\n [36, 48, 72]\r\n])\r\n\r\nprint(\"GCD of each column:\", np.gcd.reduce(matrix, axis=0))\r\n# [ 6 3 12]\r\n\r\nprint(\"GCD of each row:\", np.gcd.reduce(matrix, axis=1))\r\n# [ 6 15 12]<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n6. Realistic examples you will actually meet<\/h3>\n
# Three machines need service every 15, 24, and 40 days\r\nservice_interval = np.array([15, 24, 40])\r\n\r\nfirst_common_day = np.lcm.reduce(service_interval) # if you have lcm\r\nprint(\"First common service day:\", first_common_day) # 120\r\n\r\n# But if we only have GCD for some reason (example)\r\nprint(\"GCD of intervals:\", np.gcd.reduce(service_interval)) # 1<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\nnumerators = np.array([12, 18, 24, 36])\r\ndenominators = np.array([30, 45, 60, 72])\r\n\r\ncommon_divisor = np.gcd(numerators, denominators)\r\n\r\nsimplified_num = numerators \/\/ common_divisor\r\nsimplified_den = denominators \/\/ common_divisor\r\n\r\nprint(\"Original fractions:\")\r\nfor n, d in zip(numerators, denominators):\r\n print(f\"{n}\/{d}\", end=\" \")\r\n\r\nprint(\"\\nSimplified:\")\r\nfor n, d in zip(simplified_num, simplified_den):\r\n print(f\"{n}\/{d}\", end=\" \")<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n# Measurements from 4 sensors over 100 time steps\r\n# Want GCD of readings per sensor (example scenario)\r\nreadings = np.random.randint(10, 200, size=(100, 4)) * 5 # multiples of 5\r\n\r\ngcd_per_sensor = np.gcd.reduce(readings, axis=0)\r\n\r\nprint(\"GCD of all readings per sensor:\", gcd_per_sensor)<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n# Multiple pairs at once\r\npairs = np.array([\r\n [12, 18],\r\n [48, 60],\r\n [7, 13],\r\n [100, 125],\r\n [0, 50]\r\n])\r\n\r\nprint(\"GCD of each pair:\")\r\nprint(np.gcd(pairs[:,0], pairs[:,1]))\r\n# [ 6 12 1 25 50]<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n7. Summary \u2013 NumPy GCD Quick Reference<\/h3>\n
\n\n
\n \nSituation<\/th>\n Best syntax (modern NumPy)<\/th>\n<\/tr>\n<\/thead>\n \n GCD of two numbers<\/td>\n np.gcd(a, b)<\/td>\n<\/tr>\n \n Pairwise GCD of two arrays<\/td>\n np.gcd(array1, array2)<\/td>\n<\/tr>\n \n GCD of many numbers (whole array)<\/td>\n np.gcd.reduce(array)<\/td>\n<\/tr>\n \n GCD along axis (rows\/columns)<\/td>\n np.gcd.reduce(array, axis=0 or 1)<\/td>\n<\/tr>\n \n Older NumPy (before 1.18)<\/td>\n Implement with abs(a*b) \/\/ np.gcd(a,b)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Final teacher advice (very important)<\/h3>\n
lcm(a, b) = abs(a * b) \/\/ gcd(a, b)<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n