제가 지금 확장 유클리드 호제법을 이용해서 연산을 하고있는데
public static int ggcd(int r0, int r1) {
int c = r1;
int d = r0;
int x = 0;
int y = 1;
while (d != 1) {
int q = c / d;
int e = c - d * q;
int w = x - y * q;
c = d;
d = e;
x = y;
y = w;
}
if (y < 0) {
y += r1;
}
System.out.println("s :"+x+"t :"+y);
return y;
}
}
다음과 같이 작성하고 r0,r1 에 각각 12 , 67을 넣으면
역원 28이 나오는건 맞는데
sr0+tr1에서
s가 -5가 나와야 하는데 -11이 나옵니다...
다른 수를 넣어도 역원은 잘 나오는거 같은데 s가 자꾸 이상하게 나와요 ㅜㅜ 도움 부탁드립니다.