C++ :

#include<iostream>
using namespace std;
int d,x,y;
void exgcd(int a,int b)
{
	if(!b){d=a;x=1;y=0;}
	else {exgcd(b,a%b);
	int t=x;x=y;y=t-a/b*y;}
}
int main()
{
    int a,n;
    cin>>a>>n;exgcd(a,n);
    x%=n;while(x<0)x+=n;
    cout<<x;
	return 0;
}

Pascal :

var a,b,x,y,k:longint;
function ex(a,b:longint; var x,y:longint):longint;
var t:longint;
begin
  if b=0 then
  begin x:=1;y:=0;exit(a);end;
  ex:=ex(b,a mod b,x,y);
  t:=x;
  x:=y;
  y:=t-(a div b)*y;
end;
begin
  readln(a,b);
  k:=ex(a,b,x,y);
  writeln((x+b)mod b);
end.

Java :

import java.util.Scanner;

class data_{
	int x;
	int y;
}
public class Main {
	public static void main(String[] args) {
		Scanner cin=new Scanner(System.in);
		int a=cin.nextInt();
		int b=cin.nextInt();
		data_ da=new data_();
		int d=exGcd(a,b,da);
//		da.x+ny=0;
		if (da.x<0) {
			int ans=-da.x%b==0?0:(-da.x/b+1)*b+da.x;
			System.out.println(ans);
		}
		else {
			System.out.println(da.x);
		}
	}
	public static int exGcd(int a,int b,data_ d) {  
		if(b==0)   
		{    
			d.x=1;d.y=0;   
			return a;   
		 }   
		int r=exGcd(b,a%b,d);  
		int t=d.x;
		d.x=d.y;
		d.y=t-a/b*d.y;   
		return r; 
		} 
}