0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Nov 5 '17 at 11:20
  • $\begingroup$ 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". $\endgroup$ Nov 5 '17 at 13:05
  • $\begingroup$ $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$. $\endgroup$
    – user236182
    Nov 5 '17 at 13:24
  • $\begingroup$ 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 $\endgroup$ Nov 5 '17 at 13:44
0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$ Nov 5 '17 at 15:12
  • $\begingroup$ oh i see. you substituted into the first equation. the last sentence still stands $\endgroup$ Nov 5 '17 at 15:16
  • $\begingroup$ 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! $\endgroup$ Nov 5 '17 at 15:18
  • $\begingroup$ @JamesDoe1246 Whole numbers may have different definitions. Use the word "integers" to be clear. And no problem. $\endgroup$
    – user236182
    Nov 5 '17 at 15:22
  • $\begingroup$ yeah youre right. i just couldnt come up with the right word for it since Im not used to english maths terms. thanks $\endgroup$ Nov 5 '17 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.