```python
%matplotlib inline
from IPython.display import display,Math
from sympy import *
init_session()
```

    IPython console for SymPy 1.8 (Python 3.7.10-64-bit) (ground types: gmpy)
    
    These commands were executed:
    >>> from __future__ import division
    >>> from sympy import *
    >>> x, y, z, t = symbols('x y z t')
    >>> k, m, n = symbols('k m n', integer=True)
    >>> f, g, h = symbols('f g h', cls=Function)
    >>> init_printing()
    
    Documentation can be found at https://docs.sympy.org/1.8/
    



```python
%%time
# ユークリッドの互除法
a, b = 20210608, 80601202
r = a%b
count = 1
while r != 0:
    a,b = b,r
    r = a%b
    count += 1
print(b,count)
```

    22 16
    CPU times: user 57 µs, sys: 0 ns, total: 57 µs
    Wall time: 60.3 µs



```python
%%time
# ユークリッドの互除法　余りの改良
a, b = 20210608, 80601202
r = a%b
count = 1
while r != 0:
    a,b = b,r
    r = a%b
    count += 1
    if b < 2*r:
        r = b-r
print(b,count)
```

    22 11
    CPU times: user 239 µs, sys: 56 µs, total: 295 µs
    Wall time: 208 µs



```python
# 拡張ユークリッドの互除法
def myexgcd(a,b):
    x, y, u, v = 1, 0, 0, 1
    while b != 0:
        q = a // b
        x -= q * u
        y -= q * v
        x, u = u, x
        y, v = v, y
        a, b = b, a % b
    return x, y
```


```python
# 動作確認
a,b = 123,321
x,y = myexgcd(a,b)
print("{:d}*{:d}{:+d}*{:d}={:d}".format(x,a,y,b,x*a+y*b))
```

    47*123-18*321=3



```python
from ipywidgets import interact
import time
def myexgcd(a,b):
    x, y, u, v = 1, 0, 0, 1
    while b != 0:
        q = a // b
        x -= q * u
        y -= q * v
        x, u = u, x
        y, v = v, y
        a, b = b, a % b
    return x, y
@interact
def _(a="314159265",b="35"):
    digits = len(b)
    a,b = int(a),int(b)
    x,y = myexgcd(a,b)
    return display(Math("{:d}*{:d}{:+d}*{:d}={:d}".format(x,a,y,b,x*a+y*b)))
```




    interactive(children=(Text(value='314159265', description='a'), Text(value='35', description='b'), Output()), …




```python

```

7666bd0ab10e350b2e14214f83fb7527863e26ab
ipynb
Jupyter Notebook
21jk1-0616.ipynb
ritsumei-aoi/21jk1
2d49628ef8721a507193a58aa1af4b31a60dfd8b
Apache-2.0
21jk1-0616.ipynb
ritsumei-aoi/21jk1
2d49628ef8721a507193a58aa1af4b31a60dfd8b
Apache-2.0
21jk1-0616.ipynb
ritsumei-aoi/21jk1
2d49628ef8721a507193a58aa1af4b31a60dfd8b
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES