# Finding Bézout coefficients for GCD(3n+1, 2n-1)

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

• well yeah. if n can be written as 3+5k then the bezout coef of 3n+1, 2n-1 are 3 and -5. I dont really care about that tho. I care about when n is not 3+5k Nov 5 '17 at 11:20
• oh my bad. I wrote the wrong coefficients from my notes. It is supposed to be 2, -3. That is 6k+2-6k+3 = 5. I will correct it in the post. Thank you for pointing this out but still doesnt "help my problem". Nov 5 '17 at 13:05
• $a,b\in\mathbb Z$ such that $a(3n+1)+b(2b-1)=1$ for all $n\not\equiv 3\pmod{5}$ do not exist. If $n=0\not\equiv 3\pmod{5}$, then $a-b=1$. If $n=1\not\equiv 3\pmod{5}$, then $4a+b=1$. Add these equalities. $5a=2$. Contradiction, because $5$ doesn't divide $2$. Nov 5 '17 at 13:24
• ok thank you. this makes sense. but I think there should be a way of finding a,b ∈Z, where a,b can be expressed using the n. this shows that there isnt one particular solution for all of them. but I would like to find a relation between a,b and n Nov 5 '17 at 13:44

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$$

• i think I understand everything except the 5a+2nh−2=h where did it come from? and also why do you assume h−2nh+2 ≡ 0 (mod 5) Nov 5 '17 at 15:12
• oh i see. you substituted into the first equation. the last sentence still stands Nov 5 '17 at 15:16
• oh again. yea I know!! because a is whole number. this is cool. Thank you very much. You helped me enourmously! I think I understand it way better now! Nov 5 '17 at 15:18
• @JamesDoe1246 Whole numbers may have different definitions. Use the word "integers" to be clear. And no problem. Nov 5 '17 at 15:22
• yeah youre right. i just couldnt come up with the right word for it since Im not used to english maths terms. thanks Nov 5 '17 at 15:27