DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Modular Linear Equation Solver

06.22.2007
| 8100 views |
  • submit to reddit
        Prints the roots of this equation:
ax = b (mod n)

Relies on Euclid's extended algorithm:
http://snippets.dzone.com/posts/show/4192

def solveLinearModularEquation(a, b, n):
  d, xx, yy = euclidExtended(a, n)
  if (b % d == 0):
    x0 = (xx * (b / d)) % n
    for i in xrange(0, d):
      print (x0 + i * (n / d)) % n,
  else:
    print "No solution"
  print