he-013

# HumanEval/13

Implement a file **`solution.py`** that completes the function below. Keep the given name and signature; your file must define it at module level.

```python


def greatest_common_divisor(a: int, b: int) -> int:
    """ Return a greatest common divisor of two integers a and b
    >>> greatest_common_divisor(3, 5)
    1
    >>> greatest_common_divisor(25, 15)
    5
    """
```

<!-- imported from OpenAI HumanEval (HumanEval/13) -->

# Auto-generated from OpenAI HumanEval HumanEval/13. Do not edit by hand.
from solution import *  # noqa: F401,F403 (prompt helpers may be referenced by tests)
from solution import greatest_common_divisor as candidate

METADATA = {
    'author': 'jt',
    'dataset': 'test'
}


def check(candidate):
    assert candidate(3, 7) == 1
    assert candidate(10, 15) == 5
    assert candidate(49, 14) == 7
    assert candidate(144, 60) == 12


def test_he_013():
    check(candidate)

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
def greatest_common_divisor(a: int, b: int) -> int:
    """ Return a greatest common divisor of two integers a and b
    >>> greatest_common_divisor(3, 5)
    1
    >>> greatest_common_divisor(25, 15)
    5
    """
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a
```

The user wants me to implement the `greatest_common_divisor` function in Python. This is a classic problem that can be solved using the Euclidean algorithm.

The function should:
1. Take two integers a and b
2. Return their greatest common divisor (GCD)

The Euclidean algorithm works as follows:
- gcd(a, b) = gcd(b, a mod b)
- Continue until b becomes 0
- Then gcd(a, 0) = a

I can implement this iteratively or recursively. I'll use an iterative approach for efficiency.

Let me write the solution:

```python
def greatest_common_divisor(a: int, b: int) -> int:
    """ Return a greatest common divisor of two integers a and b
    >>> greatest_common_divisor(3, 5)
    1
    >>> greatest_common_divisor(25, 15)
    5
    """
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a
```

This handles:
- Positive integers
- Negative integers (by taking absolute values)
- Zero cases (gcd(a, 0) = |a|)

Let me verify with the examples:
- gcd(3, 5): a=3, b=5 → a=5, b=3 → a=3, b=2 → a=2, b=1 → a=1, b=0 → return 1 ✓
- gcd(25, 15): a=25, b=15 → a=15, b=10 → a=10, b=5 → a=5, b=0 → return 5 ✓

This looks correct.