module NumberTheory::Congruences

Public Class Methods

chinese_remainder_theorem(remainders, modulos) click to toggle source

Returns an integer d satifying the following simultaneous congruences x ≡ r1 (mod m1) x ≡ r2 (mod m2) x ≡ r3 (mod m3) and 0 <= d < m1*m2*m3

Example

>> Congruences.chinese_remainder_theorem([2, 3, 2], [3, 5, 7])
=> 23
the above solves
# x ≡ 2 (mod 3)
# x ≡ 3 (mod 5)
# x ≡ 2 (mod 7)
# File lib/number-theory/congruences.rb, line 50
def self.chinese_remainder_theorem(remainders, modulos)
  m1 = modulos[0].abs
  m2 = modulos[1].abs
  m3 = modulos[2].abs
  r1 = remainders[0]
  r2 = remainders[1]
  r3 = remainders[2]
  arr = Divisors.extended_euclidean_algo(m1, m2)
  g1 = arr[0]
  g2 = Divisors.euclidean_algo(m2, m3)
  g3 = Divisors.euclidean_algo(m3, m1)
  if g1 != 1 || g2 != 1 || g3 != 1
    false
  else
    # x ≡ r1 (mod m1) ...... (1)
    # x ≡ r2 (mod m2) ...... (2)
    # x ≡ r3 (mod m3) ...... (3)
    # From (1) and (2), we have m1*q1 + r1 ≡ r2 (mod m2)
    # which means m1*q1 - m2*q2 = r2 - r1
    # So, we can solve this linear congruence equation for x0 which equals m1*q1 + r1
    # Then, we can assume x0 + m1*m2*y ≡ r3 (mod m3)
    # which means m1*m2*y - m3*q3 = r3 - x0
    # So, we have the following solution
    q1 = arr[1] * (r2 - r1)
    x0 = m1 * q1 + r1
    arr2 = Divisors.extended_euclidean_algo(m1*m2, m3)
    x = (arr2[1] * (r3 - x0) * m1 * m2 + x0) % (m1*m2*m3) # Make sure 0 <= x < m1*m2*m3
    x
  end
end
linear_congruences_solver(a, c, m) click to toggle source

Returns all the incongruent solutions to ax ≡ c (mod m) in ascending order

Example

>> Congruences.congruences_solver(893, 266, 2432) # this solves 893x ≡ 266 (mod 2432)
=> [82, 210, 338, 466, 594, 722, 850, 978, 1106, 1234, 1362, 1490, 1618, 1746, 1874, 2002, 2130, 2258, 2386]
# File lib/number-theory/congruences.rb, line 13
def self.linear_congruences_solver(a, c, m)
  return [] if a == 0 || m == 0
  # Assuming both a and m are positive integers
  # If negative values are passed, they will be treated as positive integers
  a = 0 - a if a < 0
  m = 0 - m if m < 0
  arr = Divisors.extended_euclidean_algo(a, m)
  gcd = arr[0]
  if c % gcd != 0
    [] # i.e no solution
  else
    first = (arr[1] * c / gcd) % m
    sol = [first]
    i = 1
    while i < gcd do
      x = first + i * m / gcd
      x -= m if x >= m
      sol << x
      i+=1
    end
    sol.sort
  end
end