#!/usr/bin/env python
# coding: utf-8

# #Наибольший общий делитель

# ##Реализация алгоритма Евклида нахождения НОД

# In[1]:


def euclid(a, b):
    '''
    Алгоритм Евклида
    Возвращает НОД(a, b), где a, b – целые
    '''
    a = abs(a)
    b = abs(b)
    while b > 0:
        a, b = b, a % b
    return a 


# ###Пример

# In[2]:


euclid(88179, 5313)


# ##Реализация расширенного алгоритма Евклида:

# In[3]:


def ext_euclid(a, b):
    '''
    Расширенный алгоритм Евклида
    Возвращает (d, u, v), где d = НОД(a, b) и u*a + v*b = d
    '''
    u_prev, v_prev = 1, 0
    u,      v      = 0, 1
    if a < 0:
        a = -a
        u_prev = -1
    if b < 0:
        b = -b
        v = -1
    while b > 0:
        q = a // b
        a, b = b, a % b
        u_prev, u = u, u_prev - q*u    
        v_prev, v = v, v_prev - q*v    
    return a, u_prev, v_prev 


# ###Пример

# In[4]:


a = 88179
b = 5313
d, u, v = ext_euclid(a, b)
print d, u, v


# ###Проверка

# In[5]:


u*a + v*b