Monday, July 4, 2016

number theory - Finding X and Y for given equation

Given two numbers $A$,$B$. Let $G$ be the GCD of two numbers. I need to tell the values of $X$ and $Y$ such that


$$ G = X A + Y B $$


How to approach this problem ? Like if we have $A=25$ and $B=45$ then GCD , $G=5$.


So $5 = 2 \times 25 - 1 \times 45$. Hence here $X=2$ and $Y=-1$.


So how to tackle this problem for given $A$ and $B$?


My try :


int a=25;
int b=45;

int s=0;
int old_s=1;
int t=1;
int old_t=0;
int r=b;
int old_r=a;
while(r!=0){
int quotient = old_r / r;
old_r = r;
r = old_r-quotient * r;

old_s = s;
s = old_s - quotient * s;
old_t = t;
t = old_t - quotient * t;
}
cout<< old_s << " " << old_t<cout<< old_r <cout<< t << " " << s <

Whats wrong with this code ?

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...