Matt23

Modular equation solver

Nov 29th, 2015
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.18 KB | None | 0 0
  1. # -*- coding: utf-8 -*-
  2.  
  3. #
  4. # ax ≡ b (mod c)
  5. # Looking for two smallest positive numbers (x) satisfying equation ax - b ≡ 0 (mod c)
  6. # Having two solutions m & n is possible to determine formula for all solutions
  7. #
  8. # n - m is a difference between next solutions; m is smaller then n;
  9. # Hence if ax = b (mod c), x = (n - m)t + m
  10. #
  11.  
  12. def getEquation(a, b, c):
  13.     if a is c and b is not 0 and b is not c:
  14.         return "There is no solution"
  15.  
  16.     congruent = u"\u2261".encode('utf-8')
  17.     answer = "{0}x {1} {2} (mod {3}) \n".format(a, congruent, b, c) # ax ≡ b (mod c)
  18.     if a %c is not a or b % c is not b:
  19.         answer += "{0}x {1} {2} (mod {3}) \n".format(a % c, congruent, b % c, c)
  20.  
  21.     solutions, i = [], 0
  22.     a %= c
  23.     b %= c
  24.  
  25.     while len(solutions) is not 2:
  26.         if i > 2 * c: return "There is no solution"
  27.         if (a * i - b) % c is 0: solutions.append(i)
  28.         i += 1
  29.  
  30.     answer += "x {0} {1} (mod {2}) \n".format(congruent, solutions[0], solutions[1] - solutions[0]) # x ≡ m (mod n - m)
  31.     answer += "x = {0}t + {1}".format(solutions[1] - solutions[0], solutions[0]) # x = (n - m)*t + m
  32.     return answer
  33.  
  34. print(getEquation(411, 3207, 911))
Advertisement
Add Comment
Please, Sign In to add comment