[정수론](-)[ax+by+cz=1]

정수론 과제 중...

문제: 1. 방정식 ax+by+cz = 1이 정수해를 가지는 조건은 무엇인가?

         2. 해가 존재한다면 일반해를 찾는 방법은 무엇인가?

         3. 예시로 155x+341y+385z=1의 정수해를 찾아라

 

1. 방정식 ax+by+cz = 1이 정수해를 가지는 조건은 무엇인가?

a, b, c의 순서는 고려하지 않아도 된다.

추측: gcd(a, b, c) = 1 이라면 ax+by+cz = 1이 정수해를 가진다.

by 선형방정식 정리,

    ax+by=gcd(a, b)를 만족하는 해인(x1, y1) (단, x1, y1은 정수)를 구할 수 있다
    따라서 정수 p에 대해 p(ax+by) = pgcd(a, b)를 통해 gcd의 p배를 만드는 해도 찾을 수 있다.

따라서 ax+by+cz=1를 pgcd(a, b)+cz=1로 변형하자.

gcd(a, b, c) = gcd(gcd(a, b), c) 이므로, 선형방정식 정리를 사용한다면

pgcd(a, b)+cz=1 또한 항상 만족하는 정수해가 있다는 것을 알 수 있다.

따라서 gcd(a, b, c) = 1이면 ax+by+cz = 1이 정수해를 가진다는 참이다.

 

2. 해가 존재한다면 일반해를 찾는 방법은 무엇인가?

by 선형방정식 정리, ax+by=gcd(a, b)=g에서

일반해는 (x1+bk/g, y1-ak/g) (단, k는 정수)이다.

gcd의 p배로 만드는 해는 (p(x1+bk/g), p(y1-ak/g))이다.

gcd(a, b)p +cz = 1에서 어떤 근이 (p1, z1)이라 한다면 

선형방정식 정리에 의해 일반해는 (p1+cn, z1-gn) (단, n은 정수) 이다.

따라서 이 두 식을 합치면 결과적으로

(x, y, z) = ((p1+cn)(x1+bk/g), (p1+cn)(y1-ak/g), z1-gn)이다.

 

3. 155x+341y+385z=1의 정수해를 찾아라

유클리드 호제법으로 ax+by=gcd(a, b)의 (x1, y1)을 찾으면

(x1, y1) = (-2, 1)

그 다음 gp + cz = 1에 대해서도 유클리드 호제법을 사용한다면

(p1, z1) = (-149, 12)이다.

위에서 나온 해를 바탕으로 a, b, c, x1, y1, z1, g, p를 일반해에 대입하면

(x, y, z) = ((-149+385n)(-2+11k), (-149+385n)(1-5k), 12-31n) (단, n, k는 정수)

 

아래 코드로 계산하면 정수해의 예시로

k=1, n=1일때, (2124, -944, -19)

k=2, n=1일때, (4729, -2124, -19)

k=1, n=2일때, (5589, -2484, -50)

'''
ax+by+cz=1의 일반해 구하기
k, n 두 수에 따라 일반해가 출력됨
'''

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def extended_gcd(a, b):
    if b == 0:
        return 1, 0  # 해는 (1, 0)
    
    x1, y1 = extended_gcd(b, a % b)  # 재귀 호출
    x = y1
    y = x1 - (a // b) * y1
    
    return x, y


# user parameter
a = 155
b = 341
c = 385

n = 2
k = 1

# calculation
g = gcd(a, b)

x1, y1 = extended_gcd(a, b)
p1, z1 = extended_gcd(g, c)

x = (p1+c*n)*(x1+b/g*k)
y = (p1+c*n)*(y1-a/g*k)
z = z1 - g*n

calc = a*x + b*y + c*z
print("k = %d, n = %d 일때" %(k, n))
print("x: %d\ny: %d\nz: %d" %(x, y, z))
print("검산: %d * %d + %d * %d + %d * %d = %d" %(a, x, b, y, c, z, calc))