제가 지금 확장 유클리드 호제법을 이용해서 연산을 하고있는데

 

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가 자꾸 이상하게 나와요 ㅜㅜ 도움 부탁드립니다.