(a,b)
| 79 | return possible |
| 80 | |
| 81 | def egcd(a,b): |
| 82 | # Extended Euclidean Algorithm |
| 83 | # returns x, y, gcd(a,b) such that ax + by = gcd(a,b) |
| 84 | u, u1 = 1, 0 |
| 85 | v, v1 = 0, 1 |
| 86 | while b: |
| 87 | q = a // b |
| 88 | u, u1 = u1, u - q * u1 |
| 89 | v, v1 = v1, v - q * v1 |
| 90 | a, b = b, a - q * b |
| 91 | return u, v, a |
| 92 | |
| 93 | def gcd(a,b): |
| 94 | # 2.8 times faster than egcd(a,b)[2] |