I have this problem. I need to somehow find the bézout coefficients for numbers that are 3n+1,2n-1 for n natural. I know that GCD(3n+1,2n-1) is either 5 or 1 thanks to euclid algorithm that shows GCD(3n+1,2n-1)=GCD(5,n-3). I can easily represent 5 = 2*(3n+1) + (-3)*(2n-1) for any n = 3+5k (for every k=0,1,2,....)
So basically I need to find a*(3n+1)+b*(2n-1)=1
I have came up with a formula but I dont know how to "reason it". Also it is not perfect because I think it should be easier. Lets say a,b are bezout coef for gcd(3n+1,2n-1) = 1 and c, d are bezout coef for gcd(n-3,5) = 1
I can write
a=d*2+(-1)*c
b=d*(-3)+2*c
Thats where I stopped and dont know how to make it simple. Any ideas? Thank you
By Euclidean algorithm: $$\gcd(3n+1,2n-1)=$$
$$=\gcd((3n+1)+(2n-1),2n-1)=$$
$$=\gcd(5n,2n-1)$$
$\gcd(n,2n-1)=1$, so $$=\gcd(5,2n-1)$$
$$2n\equiv 1\equiv 6\pmod{5}\stackrel{:2}\iff n\equiv 3\pmod{5}$$
$$\gcd(3n+1,2n-1)=\gcd(5,n-3)$$
You want to find $a,b\in\mathbb Z$ such that $a(3n+1)+b(2n-1)=1$ when $n\not\equiv 3\pmod{5}$.
If $\exists a,b\in\mathbb Z$ such that $a(3n+1)+b(2n-1)=1$ for all $n\not\equiv 3\pmod{5}$, then when $n=0\not\equiv 3\pmod{5}$, $a-b=1$, when $n=1\not\equiv 3\pmod{5}$, $4a+b=1$, add these equalities, $5a=2$, but $5$ does not divide $2$, contradiction.
You can find $a,b$ for one $n$, $n\not\equiv 3\pmod{5}$.
$$n(3a+2b)=1-a+b$$
$$1-a+b=nh,\, h\in\mathbb Z$$
$$b=nh+a-1$$
$$5a+2nh-2=h$$
$$a=\frac{h-2nh+2}{5}$$
$$h-2nh+2\equiv 0\pmod{5}$$
$$h(2n-1)\equiv 2\pmod{5}$$
You know $n\not\equiv 3\pmod{5}$, so $2n-1\not\equiv 0\pmod{5}$, so modulo multiplicative inverse exists.
$$h\equiv 2(2n-1)^{-1}\pmod{5}$$
$$h=5t+2((2n-1)^{-1}\bmod 5),\, t\in\mathbb Z$$
$$a=\frac{1}{5}(5t+2((2n-1)^{-1}\bmod 5)-$$
$$-10nt-4n((2n-1)^{-1}\bmod 5)+2)$$
$$b=n(5t+2((2n-1)^{-1}\bmod 5))+$$
$$+\frac{1}{5}(5t+2((2n-1)^{-1}\bmod 5)-$$
$$-10nt-4n((2n-1)^{-1}\bmod 5)+2)-1$$