디오판토스방정식이란 a*x+b*y = i*gcd(a,b)꼴로 되어있는 방정식을 말합니다
만약 a*x+b*y = c이고
gcd(a,b)|c가 참이 되지않는다면 이 방정식에 x와 y는 존재하지않습니다 gcd(a,b) = d라하겠습니다
Q. 어디에 쓰냐!!!!!!
A. 아이스크림 200개를 가진 아저씨가 구름학교 전교생 x명에게 10개씩 아이스크림을 나눠주고 정신학교 전교생 y명에게 20개씩 아이스크림을 나누어줬을때 남은 아이스크림은 100개일때 구름학교 전교생과 정신학교 전교생의 수가 될수있는 수를 모두 구하시오...ㄱ
와 같은 문제를 쉽게 풀수있답니다 저 문제의 식을 세우면 10x+20y = 100 입니다
우리는 이 방정식을 풀기위해 유클리드 호제법이라는 개념을 사용하겠습니다 하나의 해를 찾을겁니다 유클리드 호제법으로 10와 20의 최대공약수를 전개합니다 20 = 10*2+0
유클리드 호제법을 역으로 전개하여 10 = 20-10*1...ㄴ 를 얻는데 10x+20y = 100에서 10으로 양변을 나누면 x+2y = 10 이되며 식 ㄴ에서 2*10-1*10이되며 즉 x = -1*10 y = 1*10 이 하나의 해를 특성해
라고 하며 디오판토스방정식의 일반해는
x = (b/d)*k+x_0, y = k*(-a/d)+y_0입니다 x = 2k-10 y = -k+10
직접 대입해보죠 20k-100-20k+200 = 100 와우
그리고 학생수는 양수여야되니까 6<=k이며 k<=9입니다
그러면 순서쌍 4개를 이렇게 대입해서 쓰면되겠죠?
이제 다른 방식으로 풀어볼겁니다
잉여 역수라는 수로 풀어볼것인데
a는 상수고 잉여역수는
a*b 가 m으로 나눠 1이남을때 b를 법 m에대한 a의 잉여역수라합니다
아까 10x+20y = 100을 합동식으로 바꿔봅시다 나머지정리에서 10x ≡ 100 (mod 20) 20으로 또 나눈나머지는 10x≡0(mod 20) 10b ≡ 1 (mod 20)에서 잉여역수를 구할겁니다
다시 디오판토스방정식으로 변형하면 10b+20y = 1이되는데 10과 20의 최대공약수가 1을 나누지않으므로 잉여역수가 존재하지않습니다
또 10|20이므로 x = 2k꼴이고 20k+20y = 100에서 20y = 100-20k, y = 5-k 이다
이건 잉여역수가없어서 보여주지못했지만 잉여역수를 합동식에 곱하면 상수부분이 1로 변해서 바로 x의 꼴을 구할수있게됩니다
참고로 합동식을 모르는 분께 설명드리자면 그냥 나머지입니다 a ≡ b (mod m)이면 a를 m으로 나눈나머지가 b라는것입니다
