(정수론/파이썬) 합동방정식/선형방정식 정수해 구하기

# 선형방정식 & 합동방정식 해 구하기

# 1) 선형방정식 해 구하기
# '친절한 수론 길라잡이' 8장 합동 61쪽
# 893 * x ≡ 266 (mod 2432) 를 선형방정식으로 표현하면,
# 893 * x - 2432 * y = 266
# 와 같은데, x와 y의 해를 단순하게 0부터 적당한 숫자까지 대입하여 검사하는 루틴이다.
# 
# 함수 호출은 다음과 같이 한다.
# linear_equation_compute(a, b, c)
# a : 893
# b : 2432
# c : 266
# 정답을 gcd(a, b) 갯수만큼 출력한다.

# gcd 구하는 함수 numpy.gcd()를 사용해도 된다
def my_gcd(a, b):
    if a == b:
        return a
    if a < b:  # a > b 조건을 맞추기 위해 두 값을 맞바꾸기
        tmp = a
        a = b
        b = tmp
    r0 = a
    r1 = b
    for i in range(b): # 두 수 증 작은 수만큼 최대 반복
        r2 = r0 % r1 # 몫은 필요 없으므로 나머지만 구함
        
        if r2 == 0: # 나머지가 0이라면
            return r1 # 직전의 나머지가 최대공약수임
        # 값들을 한칸씩 shift 시켜서 다시 반복
        r0 = r1
        r1 = r2

# 893 * x - 2432* y = 266
#   a * x - b * y =  c
def linear_equation_compute(a, b, c):
  g = my_gcd(a, b)
  lst = []
  if c % g != 0:
    #print("정수해가 없습니다.")
    return lst
  count = 0
  for i in range(1, b):
    r = (a * i - c) % b
    if r == 0:
      y = (a * i - c) // b
      lst.append((i, y))
      #print(i, y)
      count += 1
      if count >= g:
        break
  return lst


# 2) 합동방정식 해 구하기
# '친절한 수론 길라잡이' 65쪽 연습문제 8.7
# ax = c (mod m)
# 합동방정식의 해가 있다면 gcd(a, m) | c 이므로, 
# gcd로 세 값을 모두 나눈 것을 da, gm, dc라 하면,
# da*x = dc (mod dm) 은 단 하나의 해를 가진다.
# 이 해를 x1 이라 하면, 해의 갯수는 모두 g개가 된다.
# 모든 해 = {x | x1 + dm * k, k는 0, 1, 2, ..., g-1}
# linear_equation_compute 도 같은 역할을 하는데, 단순하게 대입해서 계산하므로, 수가 커지면
# congruence_equation 함수가 훨씬 빠르게 작동한다.

def congruence_equation(a, c, m):
  g = my_gcd(a, m)  
  lst = []
  if c % g != 0:
    #print(f"gcd({a}, {m}) = {g} : {c}을 나눌 수 없습니다. 정수해가 없습니다.")
    return lst
  da = a // g  # 3
  dc = c // g  # 2
  dm = m // g  # 13
  for i in range(0, dm):
    r = (da * i - dc) % dm
    if r ==0:
      # 정답은 i
      #y = (a * i - c) // m # 정답은  (i, y) => (x, y)
      break
  for k in range(0, g):
    x = i + dm*k
    lst.append(x)
  return lst
      

lst = linear_equation_compute(3, 13, 2)
print("{}개 : {}".format(len(lst), lst))

# gcd(943, 2576) = 23, 23은 381을 나누지 못함. 따라서 정수해가 없음.
lst = linear_equation_compute(943, 2576, 381)
print("{}개 : {}".format(len(lst), lst))

# gcd(893, 2432) = 19, 19는 266을 나눔, 따라서 19개의 다른 해를 가짐
lst = linear_equation_compute(893, 2432, 266)
print("{}개 : {}".format(len(lst), lst))

# gcd(4183, 15087) = 47 즉 47개의 해
lst = linear_equation_compute(4183, 15087, 5781)
print("{}개 : {}".format(len(lst), lst))

# 총 7개 (5, 18, 31, 44, 57, 70, 83)
lst = linear_equation_compute(21, 91, 14)
print("{}개 : {}".format(len(lst), lst))

print("------------------------------")

lst = congruence_equation(3, 2, 13)
print("{}개 : {}".format(len(lst), lst))

lst = congruence_equation(943, 381, 2576)
print("{}개 : {}".format(len(lst), lst))

lst = congruence_equation(893, 266, 2432)
print("{}개 : {}".format(len(lst), lst))

lst = congruence_equation(4183, 5781, 15087)
print("{}개 : {}".format(len(lst), lst))

lst = congruence_equation(21, 14, 91)
print("{}개 : {}".format(len(lst), lst))

결과:

1개 : [(5, 1)]
0개 : []
19개 : [(82, 30), (210, 77), (338, 124), (466, 171), (594, 218), (722, 265), (850, 312), (978, 359), (1106, 406), (1234, 453), (1362, 500), (1490, 547), (1618, 594), (1746, 641), (1874, 688), (2002, 735), (2130, 782), (2258, 829), (2386, 876)]
47개 : [(225, 62), (546, 151), (867, 240), (1188, 329), (1509, 418), (1830, 507), (2151, 596), (2472, 685), (2793, 774), (3114, 863), (3435, 952), (3756, 1041), (4077, 1130), (4398, 1219), (4719, 1308), (5040, 1397), (5361, 1486), (5682, 1575), (6003, 1664), (6324, 1753), (6645, 1842), (6966, 1931), (7287, 2020), (7608, 2109), (7929, 2198), (8250, 2287), (8571, 2376), (8892, 2465), (9213, 2554), (9534, 2643), (9855, 2732), (10176, 2821), (10497, 2910), (10818, 2999), (11139, 3088), (11460, 3177), (11781, 3266), (12102, 3355), (12423, 3444), (12744, 3533), (13065, 3622), (13386, 3711), (13707, 3800), (14028, 3889), (14349, 3978), (14670, 4067), (14991, 4156)]
7개 : [(5, 1), (18, 4), (31, 7), (44, 10), (57, 13), (70, 16), (83, 19)]
------------------------------
1개 : [5]
0개 : []
19개 : [82, 210, 338, 466, 594, 722, 850, 978, 1106, 1234, 1362, 1490, 1618, 1746, 1874, 2002, 2130, 2258, 2386]
47개 : [225, 546, 867, 1188, 1509, 1830, 2151, 2472, 2793, 3114, 3435, 3756, 4077, 4398, 4719, 5040, 5361, 5682, 6003, 6324, 6645, 6966, 7287, 7608, 7929, 8250, 8571, 8892, 9213, 9534, 9855, 10176, 10497, 10818, 11139, 11460, 11781, 12102, 12423, 12744, 13065, 13386, 13707, 14028, 14349, 14670, 14991]
7개 : [5, 18, 31, 44, 57, 70, 83]