求解逆元

若两数a,b，gcd(a,b)=1,当存在一个s,使得as(mod b)=1;则称s为a对b的逆元；

如何求解s?

import java.util.ArrayList;
import java.util.Scanner;

public class niyuan {

    private int a,b;
    
    private static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }

    public static void main(String[] args) {
        Integer a,b,t,ta,tb;
        Scanner sc =new Scanner(System.in);
        System.out.println("请输入a:");
        a=sc.nextInt();
        System.out.println("请输入b:");
        b=sc.nextInt();
        ta=a;tb=b;
        if(gcd(a,b)!=1){
            System.out.println("gcd(a,b)不等于1");
            return;
        };
        ArrayList<Integer>arr=new ArrayList<>();
        while(a%b!=0){
            arr.add(a/b);
            t=a%b;
            a=b;b=t;
        }
        int id=arr.size()-1;
        int qa=1,qb=-arr.get(id);
        while(--id>=0){
            t=qa;
            qa=qb;
            qb=t-arr.get(id)*qb;
        }
        qa=(qa+tb)%tb;
        System.out.println("a逆 mod b:"+qa);

    }
}