2.5 The Diophantine Equation ax+by=c

The Diophantine Equation ax+by=c

디오판토스 방정식 : 2개 이상의 미지수를 갖는 방정식의 정수해를 찾는 문제
선형 디오판토스 방정식 : $ax+by=c$

• We already proved in Theorem 2.3:
  • If $d=gcd(a,b)$ , then $ax+by=d$ has a solution
• 임의의 정수 d에 대해서는?

ex

1. 3x + 6y = 18 has solutions (x,y) = (4,1) or (-6,6) or (10,-2)

2. 2x + 10y = 17 has NO solutions since 2x+10y is even, but 17 is odd

그럼 어떤 c에 대해서 해가 존재하는가?

Theorem 2.9

ex

1. 3x+6y=18 has solutions $\Longleftrightarrow gcd(3,6) = 3 \text{ and } 3 \mid 18$

2. 2x+10y=17 has NO solutions $\Longleftrightarrow gcd(2,10)=2 \text{ and } 2 \nmid 17$

pf