Question

find two integers u and v such that:20u+63v=1​

Answer 1

Since the GCD(20,63)=1, such integers do exist and there are infinitely many such pairs. Apply the Euclidean algorithm for the GCD and work backwards;

63=(3×20)+3; 20=(6×3)+2; 3=(1×2)+1 ==> 1= 3–2=3-(20–(6×3))=(7×3)-20= 7×{63-(3×20)-20=(7×63)-(22×20). Hence we may take 1=(-22)×20 +7×63 i.e. u=(-22), v=7 is a solution set. Other such pairs may be obtained by addition and subtraction of 22×63. For example 1=(-22+63)×20+(7–20)×63 = 41×20–13×63 ==> u=41, v=(-13) is another such solution. We could also have taken 1=(-22–63)×20+(7+20)×63=(-85)×20+27×63 giving u=(-85), v=27 and this procedure may be repeated as many times as wished

20u+63v=1, 20×41-63×13=820-819=1 so u=41 &v=-13.