GCD of 3 numbers, finding s, t, u
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I have to find the values s, u, t from GCD(88,99,111) = 88s + 99t + 111u
I know the GCD of this equation is 1 but I dont understand what it means by finding the values of s, t and u. Can someone please explain this to me.
number-theory greatest-common-divisor
asked Sep 2 at 12:26
mathrook1243
62
add a comment |Â
up vote
1
down vote
favorite
I have to find the values s, u, t from GCD(88,99,111) = 88s + 99t + 111u
I know the GCD of this equation is 1 but I dont understand what it means by finding the values of s, t and u. Can someone please explain this to me.
number-theory greatest-common-divisor
asked Sep 2 at 12:26
mathrook1243
62
Just find $s,t,uinBbb Z$ such that $77s+91t+143u=1$. First try to factor $77$, $91$, $143$. Then consider the above equation modulo seven. What can be said about $s,t,u$?
– dan_fulea
Sep 2 at 12:32
Use $rm GCD(a,b,c) = rm GCD(a,rm GCD(b,c))$. Now apply the extended Euclidean alg.
– Wuestenfux
Sep 2 at 12:35
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have to find the values s, u, t from GCD(88,99,111) = 88s + 99t + 111u
I know the GCD of this equation is 1 but I dont understand what it means by finding the values of s, t and u. Can someone please explain this to me.
number-theory greatest-common-divisor
asked Sep 2 at 12:26
mathrook1243
62
I have to find the values s, u, t from GCD(88,99,111) = 88s + 99t + 111u
I know the GCD of this equation is 1 but I dont understand what it means by finding the values of s, t and u. Can someone please explain this to me.
number-theory greatest-common-divisor
number-theory greatest-common-divisor
asked Sep 2 at 12:26
mathrook1243
62
asked Sep 2 at 12:26
mathrook1243
62
edited Sep 5 at 14:46
asked Sep 2 at 12:26
mathrook1243
62
asked Sep 2 at 12:26
mathrook1243
62
asked Sep 2 at 12:26
mathrook1243
62
62
Just find $s,t,uinBbb Z$ such that $77s+91t+143u=1$. First try to factor $77$, $91$, $143$. Then consider the above equation modulo seven. What can be said about $s,t,u$?
– dan_fulea
Sep 2 at 12:32
Use $rm GCD(a,b,c) = rm GCD(a,rm GCD(b,c))$. Now apply the extended Euclidean alg.
– Wuestenfux
Sep 2 at 12:35
add a comment |Â
Just find $s,t,uinBbb Z$ such that $77s+91t+143u=1$. First try to factor $77$, $91$, $143$. Then consider the above equation modulo seven. What can be said about $s,t,u$?
– dan_fulea
Sep 2 at 12:32
Use $rm GCD(a,b,c) = rm GCD(a,rm GCD(b,c))$. Now apply the extended Euclidean alg.
– Wuestenfux
Sep 2 at 12:35
Just find $s,t,uinBbb Z$ such that $77s+91t+143u=1$. First try to factor $77$, $91$, $143$. Then consider the above equation modulo seven. What can be said about $s,t,u$?
– dan_fulea
Sep 2 at 12:32
Just find $s,t,uinBbb Z$ such that $77s+91t+143u=1$. First try to factor $77$, $91$, $143$. Then consider the above equation modulo seven. What can be said about $s,t,u$?
– dan_fulea
Sep 2 at 12:32
Use $rm GCD(a,b,c) = rm GCD(a,rm GCD(b,c))$. Now apply the extended Euclidean alg.
– Wuestenfux
Sep 2 at 12:35
Use $rm GCD(a,b,c) = rm GCD(a,rm GCD(b,c))$. Now apply the extended Euclidean alg.
– Wuestenfux
Sep 2 at 12:35
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Use the extended Euclidean algorithm to find the coefficients $u$ and $v$ of a Bézout's relation between $91$ and $143$:
beginarrayrrrc
r_i& u_i&v_i&q_i \hline
143 & 0 & 1 \
91 & 1 & 0 & 1 \ hline
52 & -1 & 1 & 1 \
39 & 2 &-1 & 1 \ hline
13 & colorred-3 & colorred2 &3\
0
endarray
Thus we have $;-3cdot 91+2cdot 143=13$.
Now we need a Bézout's relation between $77$ and $13$. The extended Euclidean algorithm won't be necessary here, as there's an obvious solution: $quad6cdot 13 -77=1$.
Replacing $13$ with the first Bézout's relation, we obtain
$$-77-18cdot 91+12cdot 143=1.$$
answered Sep 2 at 13:10
Bernard
112k635104
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Use the extended Euclidean algorithm to find the coefficients $u$ and $v$ of a Bézout's relation between $91$ and $143$:
beginarrayrrrc
r_i& u_i&v_i&q_i \hline
143 & 0 & 1 \
91 & 1 & 0 & 1 \ hline
52 & -1 & 1 & 1 \
39 & 2 &-1 & 1 \ hline
13 & colorred-3 & colorred2 &3\
0
endarray
Thus we have $;-3cdot 91+2cdot 143=13$.
Now we need a Bézout's relation between $77$ and $13$. The extended Euclidean algorithm won't be necessary here, as there's an obvious solution: $quad6cdot 13 -77=1$.
Replacing $13$ with the first Bézout's relation, we obtain
$$-77-18cdot 91+12cdot 143=1.$$
answered Sep 2 at 13:10
Bernard
112k635104
add a comment |Â
up vote
2
down vote
Use the extended Euclidean algorithm to find the coefficients $u$ and $v$ of a Bézout's relation between $91$ and $143$:
beginarrayrrrc
r_i& u_i&v_i&q_i \hline
143 & 0 & 1 \
91 & 1 & 0 & 1 \ hline
52 & -1 & 1 & 1 \
39 & 2 &-1 & 1 \ hline
13 & colorred-3 & colorred2 &3\
0
endarray
Thus we have $;-3cdot 91+2cdot 143=13$.
Now we need a Bézout's relation between $77$ and $13$. The extended Euclidean algorithm won't be necessary here, as there's an obvious solution: $quad6cdot 13 -77=1$.
Replacing $13$ with the first Bézout's relation, we obtain
$$-77-18cdot 91+12cdot 143=1.$$
answered Sep 2 at 13:10
Bernard
112k635104
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Use the extended Euclidean algorithm to find the coefficients $u$ and $v$ of a Bézout's relation between $91$ and $143$:
beginarrayrrrc
r_i& u_i&v_i&q_i \hline
143 & 0 & 1 \
91 & 1 & 0 & 1 \ hline
52 & -1 & 1 & 1 \
39 & 2 &-1 & 1 \ hline
13 & colorred-3 & colorred2 &3\
0
endarray
Thus we have $;-3cdot 91+2cdot 143=13$.
Now we need a Bézout's relation between $77$ and $13$. The extended Euclidean algorithm won't be necessary here, as there's an obvious solution: $quad6cdot 13 -77=1$.
Replacing $13$ with the first Bézout's relation, we obtain
$$-77-18cdot 91+12cdot 143=1.$$
answered Sep 2 at 13:10
Bernard
112k635104
Use the extended Euclidean algorithm to find the coefficients $u$ and $v$ of a Bézout's relation between $91$ and $143$:
beginarrayrrrc
r_i& u_i&v_i&q_i \hline
143 & 0 & 1 \
91 & 1 & 0 & 1 \ hline
52 & -1 & 1 & 1 \
39 & 2 &-1 & 1 \ hline
13 & colorred-3 & colorred2 &3\
0
endarray
Thus we have $;-3cdot 91+2cdot 143=13$.
Now we need a Bézout's relation between $77$ and $13$. The extended Euclidean algorithm won't be necessary here, as there's an obvious solution: $quad6cdot 13 -77=1$.
Replacing $13$ with the first Bézout's relation, we obtain
$$-77-18cdot 91+12cdot 143=1.$$
answered Sep 2 at 13:10
Bernard
112k635104
edited Sep 2 at 22:16
answered Sep 2 at 13:10
Bernard
112k635104
answered Sep 2 at 13:10
Bernard
112k635104
answered Sep 2 at 13:10
Bernard
112k635104
112k635104
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2902673%2fgcd-of-3-numbers-finding-s-t-u%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Just find $s,t,uinBbb Z$ such that $77s+91t+143u=1$. First try to factor $77$, $91$, $143$. Then consider the above equation modulo seven. What can be said about $s,t,u$?
– dan_fulea
Sep 2 at 12:32
Use $rm GCD(a,b,c) = rm GCD(a,rm GCD(b,c))$. Now apply the extended Euclidean alg.
– Wuestenfux
Sep 2 at 12:35