Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/env python
- def euclidExtended(a, b):
- if b == 0:
- return a, 1, 0
- dd, xx, yy = euclidExtended(b, a % b)
- d, x, y = dd, yy, xx - int(a / b) * yy
- print a, b, d, x, y
- return d, x, y
- def solveLinearModularEquation(a, b, n):
- d, xx, yy = euclidExtended(a, n)
- #print d, xx, yy
- if (b % d == 0):
- x0 = (xx * (b / d)) % n
- print x0
- for i in xrange(0, d):
- print (x0 + i * (n / d)) % n,
- else:
- print "No solution."
- #ax=b(mod c)
- solveLinearModularEquation(a, b, c)
Add Comment
Please, Sign In to add comment