x,y: 고정된 정수
gcd(x+k,y+k) (k:정수)의 최댓값 구하는건데
첨에 WLOG, x<y라 하고
첨에 유클리드 알고리즘 써서
(x+k,y+k)=(x+k,y-x) 유도하면
최대공약수니까 (x+k,y-x)|y-x 나오니까
이제 (x+k,y-x)=y-x 인 k 존재한다는거 보이면 되잖아
근데 k=y-2x로 두면
(x+k,y-x)=(y-x,y-x)=y-x여서
gcd 최댓값 |y-x|로 나오는데
코딩하는데 답 자꾸 다르게나와서 돌아버리겟음
증명잘못한거임?
처음에 유클리드 호제법 쓸 때 y+k = (x+k)*1 +(y-x) 로 쓴 것 같은데 y-x < x+k 라는 보장이 없으므로 그렇게 쓰면 안 됨
a=bc+d꼴만 만들어줘도 (a,c)=(c,d)는 되는거 아니엇노?
0 =< d < b 이어야 한다. 8 = 6×0 + 8 이니까 gcd(8,6) = gcd(8,8) 인가? 당연히 아니지. 왜냐면 8=d > b=6 이므로 조건에 맞지 않기 때문