Python One-Liner: Compute GCD (Greatest Common Divisor) of Two Numbers!

Calculating the greatest common divisor (GCD)—the largest positive integer that divides two numbers without remainder—is essential in number theory, cryptography, and many algorithmic problems

Why the GCD of 360 and 48 Is 24

Euclidean Algorithm Steps

Remainder Sequence:

360 % 48 → 24

48 % 24 → 0

Once the remainder is zero, the nonzero divisor is the GCD. Therefore, GCD(360, 48) = 24

Prime Factorization Method

360 = 2³ × 3² × 5

48 = 2⁴ × 3

Common primes with lowest exponents → 2³ × 3 = 8 × 3 = 24

Long Way: Inline Euclidean Algorithm

Normalization:

Convert inputs to absolute values so the algorithm handles negative numbers correctly

Iterative Loop:

The loop while b: applies the identity

gcd(a,b)=gcd(b,amodb)

reducing the problem size each iteration until b becomes zero

Result:

When b is zero, a holds the GCD. For 360 and 48, this yields 24

One‑Liner: math.gcd()

Built‑in Convenience:

Python’s math.gcd(*integers) (available since Python 3.5) provides a single‑call solution that is highly optimized in C and handles edge cases (like zeros and negatives) gracefully

Usage Example:

import math
math.gcd(360, 48) # Returns 24

Advantages:

Concise: One line vs. several.

Performant: Lower‑level implementation for speed.

Robust: Correctly handles gcd(0, 0) == 0 and negative inputs

Practical Applications

Cryptography: Ensuring keys are co‑prime (GCD = 1) in RSA and other public‑key systems

Simplifying Fractions: Dividing numerator and denominator by their GCD for lowest terms.

Algorithm Design: Building blocks for LCM computation (lcm(a,b)=a*b//gcd(a,b)) and solving Diophantine equations (extended GCD) .

#PythonTips #CodingShorts #GCD #EuclideanAlgorithm #MathGCD #NumberTheory #CodingInterview #Algorithm #Cryptography #PythonOneLiner #CleanCode

Codes:

Long Way: Inline Euclidean algorithm

a, b = 360, 48
a, b = abs(a), abs(b)
Ensure non‑negative inputs
while b:
Repeat until b becomes zero
a, b = b, a % b
Apply (a, b) ← (b, a mod b)
print(a)
'a' now holds GCD: 24

One‑Liner: Using Python's built‑in math.gcd()

import math
Import Python’s math module
print(math.gcd(360, 48))
Compute and print GCD in one call: 24