Question

@amistre64

Answer 1

Amistre, the method you did :

237 = 81(2) + 75
81 = 75(1) + 6
75 = 6(12) + 3 <-- gcd=3
6 = 3(2) + 0

81x + 237y = 3

to find the smaller of 81 and 237, a specific value for x, we can run the reverse euclidean algorithm

0
0 1
0 - 2(1) = -2
1 -1(-2)= 3
-2-12(3) = -38 <-- x' = -38; this leaves is with y' = 13 as one soluton

Can you please explain it to me?

Answer 2

I didn't get how you did the second step (getting y' = 13 and x' = -38) .

Answer 3

the reverse euclidean algorithm follows the same basic feel of the usual euclidean algoritm

its proof is simple enough to follow, but is a pain to try to type in. Essentially it determines a recurrsive equation from the usual form

Answer 4

I understand your pain, amistre. :)

Answer 5

Ok! Well, I never studied about the reverse euclidean alogirthm, it is very interesting to know about it.

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

is this what you're talking about amistre?

Answer 6

if i were to do the "chain of pain" instead we would run this

237 = 81(2) + 75
81 = 75(1) + 6
75 = 6(12) + 3 ; 3 = 75(1) - 6(12) ; line 3
6 = 81(1) - 75(1) ; line 2
= 75(1) -(81(1)-75(1))12
= 75(13) - 81(12)
75 = 237(1) - 81(2) ; line 1
= (237(1)-81(2))13 - 81(12)
= 237(13) - 81(38)

Answer 7

yes, that wiki link is what i was refering to

Answer 8

Got it...

Answer 9

Thanks amistre, for taking pain to answer my question :) (just joking)

Thank you amistre :)

Answer 10

I had to think of a different way to recall the setup, since the book i was using made no sense to me.

from the usual algorithm we get:\[n=r_0(q_1)+r_1\\r_0=r_1(q_2)+r_2\\r_1=r_2(q_3)+r_3 \\.....\\r_{n-1}=r_n(q_{n+1})+r_{n+1}~:~such~that~r_{n+1}=gcd \\\]

the set of qs is what is important for the reverseing setup

Answer 11

Ok!

Answer 12

i first start by creating a column of the qs in this fashion

\[\begin{matrix}
-q_1\\
-q_2\\
-q_3\\
-q_4\\
....\\
-q_{n+1}\\
\end{matrix}\]


the qs get multiplied by the soluton of the row above them, and that solution keeps dropping down along a diagonal to the front

\[\begin{matrix}
&-q_1()&=&s_1\\
&-q_2(s_1)&=&s_2\\
s_1&-q_3(s_2)&=&s_3\\
s_2&-q_4(s_3)&=&s_4\\
s_3&...(s_4)&=&....\\
..&....&=&s_{n-1}\\
...&-q_{n+1}(s_{n-1})&=&x~or~y\\
\end{matrix}\]

Answer 13

Oh! Amistre , thanks a lot . I got it .

Answer 14

the value at the end depends on if we start this with a 0 1, or a 1 0

given gcd(a,b), the larger of the a or b can be determined by starting it as 1 0. the smaller by starting it as 0 1

\[\begin{matrix}
&&&0\\
&0&&1\\
0&-q_1(1)&=&s_1\\
1&-q_2(s_1)&=&s_2\\
s_1&-q_3(s_2)&=&s_3\\
s_2&-q_4(s_3)&=&s_4\\
s_3&...(s_4)&=&....\\
..&....&=&s_{n-1}\\
...&-q_{n+1}(s_{n-1})&=&small\\
\end{matrix}\]

\[\begin{matrix}
&&&1\\
&1&&0\\
1&-q_1(0)&=&s_1\\
0&-q_2(s_1)&=&s_2\\
s_1&-q_3(s_2)&=&s_3\\
s_2&-q_4(s_3)&=&s_4\\
s_3&...(s_4)&=&....\\
..&....&=&s_{n-1}\\
...&-q_{n+1}(s_{n-1})&=&large\\
\end{matrix}\]

Answer 15

have fun :)

Answer 16

:) you left me alone with this whole :(

HAHA, thanks amistre