# Source code for tryalgo.arithm

```#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
arithmetic functions

christoph dürr - jill-jênn vie - 2013-2019
"""
# pylint: disable=anomalous-backslash-in-string

# snip{ pgcd

[docs]
def pgcd(a, b):
"""Greatest common divisor for a and b

:param a,b: non-negative integers
:complexity: O(log a + log b)
"""
return a if b == 0 else pgcd(b, a % b)

# snip}

# snip{ bezout

[docs]
def bezout(a, b):
"""Bézout coefficients for a and b

:param a,b: non-negative integers
:complexity: O(log a + log b)
"""
if b == 0:
return (1, 0)
u, v = bezout(b, a % b)
return (v, u - (a // b) * v)

[docs]
def inv(a, p):
"""Inverse of a in :math:`{mathbb Z}_p`

:param a,p: non-negative integers
:complexity: O(log a + log p)
"""
return bezout(a, p)[0] % p

# snip}

# snip{ binom

[docs]
def binom(n, k):
"""Binomial coefficients for :math:`n choose k`

:param n,k: non-negative integers
:complexity: O(k)
"""
prod = 1
for i in range(k):
prod = (prod * (n - i)) // (i + 1)
return prod

# snip}

# snip{ binom_modulo

[docs]
def binom_modulo(n, k, p):
"""Binomial coefficients for :math:`n choose k`, modulo p

:param n,k: non-negative integers
:complexity: O(k)
"""
prod = 1
for i in range(k):
prod = (prod * (n - i) * inv(i + 1, p)) % p
return prod

# snip}
```