I am sure this is going to sound trivial to most of you once you figure out what I am asking.
Ok, so I am writing a post about the Euclidean algorithm and the linear equation theorem. I wrote out all the steps for the Euclidean algorithm, the steps for the linear equation theorem, and tried to be detailed as possible. There is a point in the book where they finish the process of doing a Euclidean algorithm and then take their given results and modify it using the linear equation algorithm (at least this is what I gathered).
The book gives you this as an example:
131(u) - 1008(v) = 1, they then run that through the Euclidean Algorithm and get the following
131(-277) - 1008(36) = 1
then they modify the answer to get positive values for u and v. This is what the author wrote,
u = (-277) + 1008 = 731 and v = (-36) + 131 = 95
Now, the linear equation theorem states:
Linear Equation Theorem: Let 'a' and 'b' be nonzero integers, and let g = gcd(a,b). The equation (a)(x) + (b)(y) = g always has a solution (x1, y1) in integers, and this solution can be found by the Euclidean algorithm method described earlier. Then every solution to the equation can be obtained y substituting integers 'k' into the formula:
Looking at:
u = (-277) + 1008 = 731 and v = (-36) + 131 = 95
y2 = 95, y1 = 36, a = 131. He got the equation to look like this abstractly from
y2 = y1 - (k)(a)
to
-y2 = -y1 + (k)(a); by just multiplying both sides by (-1)
I want to know why this is ok? Is it really that simple, he just moved the terms around?
You can read my actual post here for more details on the linear equation algorithm: This is not a porn link, I know you mods will be suspicious. I highly doubt a porn spammer would go to this great length of detail just to get you to click a link.
Linear Equation Theorem | Dead End Math