BEZOUT's IDENITY solution avaiable don't understand something

  • Thread starter Simkate
  • Start date
Therefore, the equation becomes 1=1-8, which is simplified to 1=-7. This shows that the first step is correct and the process can continue to find the remainders and ultimately solve for r and s. In summary, the solution to the equation 1=365r + 1876s using Bezout's Identity involves using Euclid's Algorithm to find the G.C.D, then solving for the remainders by substituting them in the equation 1=3-2*1, starting with 2, and simplifying the result to find r and s.
  • #1
Simkate
26
0
d=ar+bs

Question : 1=365r + 1876s ... Find r and s

We have to use Bezout's Identiy to solve this problem.

I have the solution already but there is a part in the solution which i don't understand, is it possible for anyone to explain me that part:

First, finding the G.C.D( which is given but the steps to it using Euclid's Algorithim)
1876=365*5 + 51
365=51*7 + 8
51=8*6 + 3
8=3*2 +2
3=2*1 +1
2=1*2 +0
Therefore the G.C.D of (365, 1876)=1

Now solving for the remainders:

0=2-1*2
1=3-2*1
2=8-3*2
3=51-8*6
8=365-51*7
51=1876- 365*5

and subsituting succesively the remainders into the equation 1=3-2*1, starting with 2:

1=3-2*1

THIS IS WHERE I AM CONFUSED NOW ::::

= 3-(8-3*2) = 3*3-8 ( i don't understand how it equals 3*3-8 ?)
=3(51-8*6)-8=3*51-8*19
.
.
.
.
.
it goes on but i first need to understand how the first step equals 3*3-8 ...if anyone could please explain!
 
Physics news on Phys.org
  • #2
Answer: The first step is a substitution of the remainder in the equation. The remainder 2 is equal to 8-3*2, so when you substitute it in the equation 1=3-2*1, you get 1=3-(8-3*2). The 3*3 simplifies to 9, and when you subtract 8 from 9 the result is 1.
 

Related to BEZOUT's IDENITY solution avaiable don't understand something

1. What is Bezout's Identity?

Bezout's Identity is a theorem in mathematics that states that for any two nonzero integers, there exist two other integers that can be multiplied with the original integers to produce their greatest common divisor (GCD).

2. How is Bezout's Identity useful in solving equations?

Bezout's Identity is useful in finding the GCD of two integers, which is a crucial step in solving linear Diophantine equations. This type of equation has the form ax + by = c, where a, b, and c are integers and x, y are unknowns. The GCD of a and b can be used to determine if the equation has any integer solutions.

3. Can Bezout's Identity be applied to non-integer numbers?

No, Bezout's Identity is only applicable to integers. However, there are similar theorems that can be used for non-integer numbers, such as the Euclidean algorithm for polynomials.

4. Are there any limitations to Bezout's Identity?

Bezout's Identity only applies to integers and cannot be used for finding the GCD of non-integer numbers. Additionally, it only works for linear Diophantine equations and cannot be applied to other types of equations.

5. How is Bezout's Identity related to the extended Euclidean algorithm?

The extended Euclidean algorithm is a method of finding the coefficients x and y in the linear Diophantine equation ax + by = c, which is the form used in Bezout's Identity. Therefore, the extended Euclidean algorithm is a practical implementation of Bezout's Identity.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
473
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
31
Views
3K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
14
Views
822
  • Calculus and Beyond Homework Help
Replies
5
Views
381
  • Calculus and Beyond Homework Help
Replies
3
Views
624
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Replies
5
Views
1K
Back
Top