# Step 1: Import the math module
import math

# Step 2: Define our numbers
num1 = 48
num2 = 18

# Step 3: Find GCD using math.gcd()
gcd_result = math.gcd(num1, num2)

# Step 4: Print the result
print(f"GCD of {num1} and {num2} is: {gcd_result}")

# Output: GCD of 48 and 18 is: 6

Step 1: 48 ÷ 18 = 2 remainder 12
Step 2: 18 ÷ 12 = 1 remainder 6
Step 3: 12 ÷ 6 = 2 remainder 0
Answer: GCD is 6 (last non-zero remainder)

def gcd_euclidean(a, b):
    """
    Find GCD using Euclidean Algorithm
    This is super efficient!
    """
    # Keep going until b becomes 0
    while b:
        # This line does the magic:
        # a becomes b, b becomes remainder of a÷b
        a, b = b, a % b
    
    # When b is 0, a contains our GCD
    return a

# Test it out
num1 = 48
num2 = 18
result = gcd_euclidean(num1, num2)

print(f"GCD of {num1} and {num2} = {result}")
# Output: GCD of 48 and 18 = 6

# Detailed step-by-step execution
def gcd_euclidean_detailed(a, b):
    print(f"Finding GCD of {a} and {b}")
    step = 1
    
    while b:
        remainder = a % b
        print(f"Step {step}: {a} ÷ {b} = {a//b} remainder {remainder}")
        a, b = b, remainder
        step += 1
    
    print(f"Final answer: {a}")
    return a

# Run the detailed version
gcd_euclidean_detailed(48, 18)

def gcd_brute_force(a, b):
    """
    Find GCD by checking all possible divisors
    Easy to understand but slower for big numbers
    """
    # Find the smaller number
    smaller = min(a, b)
    
    # Start from the smaller number and go down
    for i in range(smaller, 0, -1):
        # Check if i divides both numbers
        if a % i == 0 and b % i == 0:
            # Found our GCD!
            return i
    
    # This should never happen with positive integers
    return 1

# Test the function
num1 = 24
num2 = 36
result = gcd_brute_force(num1, num2)

print(f"GCD of {num1} and {num2} = {result}")
# Output: GCD of 24 and 36 = 12

def gcd_recursive(a, b):
    """
    Find GCD using recursion
    This mirrors the mathematical definition beautifully
    """
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)

# Test the recursive function
num1 = 56
num2 = 42
result = gcd_recursive(num1, num2)

print(f"GCD of {num1} and {num2} = {result}")
# Output: GCD of 56 and 42 = 14

gcd_recursive(56, 42)
  ↓ a=56, b=42, so call gcd_recursive(42, 56%42)
  
gcd_recursive(42, 14)
  ↓ a=42, b=14, so call gcd_recursive(14, 42%14)
  
gcd_recursive(14, 0)
  ↓ a=14, b=0, so return 14

Final result: 14

def gcd_recursive_detailed(a, b, depth=0):
    """
    Recursive GCD with detailed output
    Shows exactly what happens at each step
    """
    indent = "  " * depth
    print(f"{indent}gcd_recursive({a}, {b})")
    
    if b == 0:
        print(f"{indent}Base case reached: return {a}")
        return a
    else:
        print(f"{indent}Calling gcd_recursive({b}, {a % b})")
        result = gcd_recursive_detailed(b, a % b, depth + 1)
        print(f"{indent}Returning {result}")
        return result

# Run detailed version
print("Finding GCD of 48 and 18:")
gcd_recursive_detailed(48, 18)

from math import gcd
from functools import reduce

def find_gcd_list(numbers):
    """
    Find GCD of a list of numbers
    Uses reduce to apply gcd function repeatedly
    """
    return reduce(gcd, numbers)

# Test with multiple numbers
numbers = [24, 36, 60, 12]
result = find_gcd_list(numbers)

print(f"GCD of {numbers} = {result}")
# Output: GCD of [24, 36, 60, 12] = 12

from math import gcd

def find_gcd_manual(numbers):
    """
    Find GCD without using reduce - shows what reduce does internally
    """
    if len(numbers) < 2:
        return numbers[0] if numbers else 0
    
    result = numbers[0]
    for i in range(1, len(numbers)):
        result = gcd(result, numbers[i])
        print(f"Step {i}: gcd({result if i==1 else 'previous'}, {numbers[i]}) = {result}")
    
    return result

# Test manual version
numbers = [48, 18, 24]
print(f"Finding GCD of {numbers}:")
result = find_gcd_manual(numbers)
print(f"Final GCD: {result}")

from math import gcd

def gcd_and_lcm(a, b):
    """
    Calculate both GCD and LCM of two numbers
    Uses the mathematical relationship between them
    """
    # Calculate GCD first
    gcd_value = gcd(a, b)
    
    # Calculate LCM using the formula
    lcm_value = abs(a * b) // gcd_value
    
    return gcd_value, lcm_value

# Test the function
num1 = 12
num2 = 18
gcd_result, lcm_result = gcd_and_lcm(num1, num2)

print(f"Numbers: {num1} and {num2}")
print(f"GCD = {gcd_result}")
print(f"LCM = {lcm_result}")
print(f"Verification: {gcd_result} × {lcm_result} = {gcd_result * lcm_result}")
print(f"Original product: {num1} × {num2} = {num1 * num2}")

from math import gcd

def is_coprime(a, b):
    """
    Check if two numbers are coprime (GCD = 1)
    Essential for RSA key generation
    """
    return gcd(a, b) == 1

# Example: RSA requires coprime numbers
p, q = 61, 53  # Prime numbers
n = p * q      # Public key component
phi = (p-1) * (q-1)  # Euler's totient

# Choose e such that gcd(e, phi) = 1
e = 17
if is_coprime(e, phi):
    print(f"e = {e} is valid for RSA")
    print(f"gcd({e}, {phi}) = {gcd(e, phi)}")
else:
    print(f"e = {e} is not valid for RSA")

from math import gcd

def simplify_fraction(numerator, denominator):
    """
    Simplify a fraction using GCD
    """
    common_divisor = gcd(numerator, denominator)
    simplified_num = numerator // common_divisor
    simplified_den = denominator // common_divisor
    return simplified_num, simplified_den

# Examples
fractions = [(12, 18), (24, 36), (15, 25)]

for num, den in fractions:
    simple_num, simple_den = simplify_fraction(num, den)
    print(f"{num}/{den} simplifies to {simple_num}/{simple_den}")

from math import gcd
from functools import reduce

def find_sync_time(intervals):
    """
    Find when multiple periodic events synchronize
    Uses LCM which requires GCD
    """
    def lcm(a, b):
        return abs(a * b) // gcd(a, b)
    
    return reduce(lcm, intervals)

# Example: When do these events align?
events = {
    "Daily backup": 1,      # Every 1 day
    "Weekly report": 7,     # Every 7 days  
    "Monthly audit": 30,    # Every 30 days
}

intervals = list(events.values())
sync_day = find_sync_time(intervals)

print("Event synchronization:")
for event, interval in events.items():
    print(f"  {event}: every {interval} days")
print(f"\nAll events align every {sync_day} days")

def gcd_robust(a, b):
    """
    Handle edge cases properly
    """
    # Handle negative numbers
    a, b = abs(a), abs(b)
    
    # Handle zero cases
    if a == 0:
        return b
    if b == 0:
        return a
    
    # Regular Euclidean algorithm
    while b:
        a, b = b, a % b
    return a

# Test edge cases
test_cases = [(0, 5), (-12, 18), (15, -25), (-20, -30)]
for a, b in test_cases:
    result = gcd_robust(a, b)
    print(f"gcd({a}, {b}) = {result}")

import unittest
from math import gcd

class TestGCDFunctions(unittest.TestCase):
    
    def test_basic_gcd(self):
        """Test basic GCD calculations"""
        self.assertEqual(gcd(12, 18), 6)
        self.assertEqual(gcd(48, 18), 6)
        self.assertEqual(gcd(100, 75), 25)
    
    def test_prime_numbers(self):
        """Test GCD of prime numbers"""
        self.assertEqual(gcd(13, 17), 1)
        self.assertEqual(gcd(7, 11), 1)
    
    def test_identical_numbers(self):
        """Test GCD of identical numbers"""
        self.assertEqual(gcd(15, 15), 15)
        self.assertEqual(gcd(100, 100), 100)
    
    def test_edge_cases(self):
        """Test edge cases"""
        self.assertEqual(gcd(0, 5), 5)
        self.assertEqual(gcd(7, 0), 7)
        self.assertEqual(gcd(1, 100), 1)

# Run the tests
if __name__ == '__main__':
    unittest.main()

import time
from math import gcd

def benchmark_gcd_methods(a, b, iterations=10000):
    """
    Compare performance of different GCD methods
    """
    # Test built-in method
    start = time.time()
    for _ in range(iterations):
        result = gcd(a, b)
    builtin_time = time.time() - start
    
    # Test Euclidean method
    def gcd_euclidean(x, y):
        while y:
            x, y = y, x % y
        return x
    
    start = time.time()
    for _ in range(iterations):
        result = gcd_euclidean(a, b)
    euclidean_time = time.time() - start
    
    print(f"Built-in gcd(): {builtin_time:.4f} seconds")
    print(f"Euclidean algorithm: {euclidean_time:.4f} seconds")
    print(f"Speed difference: {euclidean_time/builtin_time:.2f}x")

# Test with large numbers
benchmark_gcd_methods(123456789, 987654321)