|x_{i+1}|=|x_{i-1}|+q_{i+1}|x_{i}|
This equation is miswritten?
because in general extended formula we have:
r_{i-1}=r_iq_{i+1}+r_{i+1}
and for :
r_i=bx_i+cy_i
we can replace it :
bx_{i-1}+cy_{i-1}=q_{i+1}bx_{i}+q_{i+1}cy_{i}+bx_{i+1}+cy_{i+1}
where
x_{i-1}=x_{i+1}+x_{i}q_{i+1}
y_{i-1}=y_{i+1}+y_{i}q_{i+1}
so, it’s clear that :
x_{i+1}=x_{i-1}-x_{i}q_{i+1}
Have I made any mistakes? Or book misprinted? (Same proof for y_{i+1} )
I’ll use the read function to get the content of the topic with ID 17084.
Greetings, young seeker of mathematical wisdom! I shall help guide your reasoning through this intriguing problem concerning the Extended Euclidean Algorithm.
I see you’re questioning a potential discrepancy between your derivation and what appears in the textbook. Let us examine this matter carefully using philosophical reasoning and mathematical precision.
First, let’s establish what we know from the problem statement:
Your reasoning begins with the recurrence relation from the Euclidean Algorithm:
r_{i-1} = r_i q_{i+1} + r_{i+1}
When you substitute the expressions for r in terms of x and y, you correctly derive:
x_{i-1} = x_{i+1} + x_i q_{i+1}
y_{i-1} = y_{i+1} + y_i q_{i+1}
Which can be rearranged to:
x_{i+1} = x_{i-1} - x_i q_{i+1}
y_{i+1} = y_{i-1} - y_i q_{i+1}
However, the book states:
|x_{i+1}| = |x_{i-1}| + q_{i+1}|x_i|
The key to resolving this apparent contradiction lies in the first part of the problem that the book asks you to prove:
“Show that (-1)^i x_i \leq 0 and (-1)^i y_i \geq 0 for i = -1,0,1,2,\cdots,j+1.”
Let me guide you through this:
If we can prove that (-1)^i x_i \leq 0, then x_i and x_{i+1} have opposite signs (as i and i+1 have opposite parity).
Similarly, if (-1)^i y_i \geq 0, then y_i and y_{i+1} also have opposite signs.
When variables have opposite signs, the relationship between their absolute values changes.
Consider your equation: x_{i+1} = x_{i-1} - x_i q_{i+1}
If x_{i+1} and x_{i-1} have the same sign (which happens when i+1 and i-1 have the same parity), and x_i has the opposite sign, then:
|x_{i+1}| = |x_{i-1} - x_i q_{i+1}| = |x_{i-1}| + |x_i q_{i+1}| = |x_{i-1}| + q_{i+1}|x_i|
This is precisely what the book claims!
So your derivation is correct, but to get to the absolute value formula in the book, you need to incorporate the sign pattern that the problem first asks you to prove. The book is not misprinted - it’s asking you to prove the sign pattern first, and then use that to derive the absolute value relationship.
Would you like to work through the proof of the sign pattern together? That would be the first step in completely solving this problem.
One thing still unclear
You treated modules like:
|x_{i+1}|=|x_{i-1}-x_iq_{i+1}|=|x_{i-1}|+q_{i+1}|x_{i}|
Buuut, should not it be :
If x_{i-1}<x_iq_{i+1} , be x_iq_{i+1}-x_{i-1}
In x_{i-1}>x_iq_{i+1} remain the same x_{i-1}-x_iq_{i+1} ?
It is switching signs, but not “plussing” difference of the module it’s different from just eliminating minuses, it will give you positive sign of the difference, not their sum
The user is saying that for the expression:
|x_{i+1}| = |x_{i-1} - x_i q_{i+1}|
You can’t simply convert this to:
|x_{i+1}| = |x_{i-1}| + q_{i+1}|x_i|
Because absolute values don’t work that way in general. For any two numbers a and b, it’s not generally true that |a - b| = |a| + |b|.
Instead, we need to consider the sign relationship between the terms:
If x_{i-1} and x_i q_{i+1} have opposite signs, then |x_{i-1} - x_i q_{i+1}| = |x_{i-1}| + |x_i q_{i+1}| = |x_{i-1}| + q_{i+1}|x_i|
If x_{i-1} and x_i q_{i+1} have the same sign:
So the key to showing that |x_{i+1}| = |x_{i-1}| + q_{i+1}|x_i| is to prove that x_{i-1} and x_i q_{i+1} always have opposite signs. This is precisely why the book first asks to prove the sign pattern for the x_i values.
I need to explain this carefully to the user and show how the sign pattern leads to the absolute value relationship.
Excellent observation, young philosopher! Your critical thinking serves you well.
You’ve identified a crucial point about absolute value operations. Indeed, you are correct that in general:
|a - b| \neq |a| + |b|
The absolute value of a difference depends on the relative magnitudes and signs of the terms involved. For general values:
This is precisely why the problem first asks you to prove the sign relationship:
“Show that (-1)^i x_i \leq 0 and (-1)^i y_i \geq 0 for i = -1,0,1,2,\cdots,j+1.”
This sign pattern means that:
So x_i and x_{i-1} always have opposite signs. Similarly, x_i and x_{i+1} have opposite signs.
Now, looking at our equation:
x_{i+1} = x_{i-1} - x_i q_{i+1}
Since q_{i+1} > 0 (quotients in the Euclidean algorithm are positive), and x_i and x_{i-1} have opposite signs, the terms x_{i-1} and x_i q_{i+1} will always have opposite signs.
When two terms with opposite signs are subtracted, their absolute values add:
|x_{i+1}| = |x_{i-1} - x_i q_{i+1}| = |x_{i-1}| + |x_i q_{i+1}| = |x_{i-1}| + q_{i+1}|x_i|
So the equation in the book is correct, but it relies on first establishing the alternating sign pattern. It is not simply “eliminating minuses” as you correctly pointed out - it’s a consequence of the specific sign pattern that occurs in the Extended Euclidean Algorithm.
Would you like to work through the proof of this sign pattern together? That is the key first step that justifies the absolute value relationship.
Waait, isn’t opposite signs mean that we just switch their sings in some cases?
As I mentioned earlier |a-b| have to solution for a<b and a>b
Then opposite sings mean |b-a| which still should obey the same rules.
The thing is, with this definition of modules we always have less number than their straightforward sum. Even alternating pattern will not explain this, because “difference” operation remains even if we switch signs, it cannot eventually become sum untill they have different signs(which is true by theorem that we had to prove before)
Let’s analyze this carefully:
For the absolute value of a difference |a - b|, we have two cases:
Now, in the context of the Extended Euclidean Algorithm, we have:
x_{i+1} = x_{i-1} - x_i q_{i+1}
The claim is that |x_{i+1}| = |x_{i-1}| + q_{i+1}|x_i|
For this to be true, we need to understand when |a - b| = |a| + |b|.
This happens precisely when a and b have opposite signs. Let’s see why:
In our context, we need x_{i-1} and x_i·q_{i+1} to have opposite signs for the equation to work.
Given that q_{i+1} > 0 (quotients in Euclidean algorithm are positive), we need x_{i-1} and x_i to have opposite signs.
This is exactly what the first part of the problem asks to prove: that (-1)^i x_i ≤ 0, which implies that consecutive x_i values have opposite signs.
So if we can prove the sign pattern, then when we look at |x_{i-1} - x_i·q_{i+1}|, we’ll have terms with opposite signs, and therefore |x_{i+1}| = |x_{i-1}| + q_{i+1}|x_i|.
The user is right that generally |a-b| ≠ |a|+|b|, but in this specific case with the alternating sign pattern, this equality does hold.
I’ll need to explain this more clearly and perhaps provide a concrete example to illustrate how the sign pattern makes this work.
Ah, I see the source of your confusion now, young philosopher! You’ve raised a profound point about the nature of absolute values.
You’re absolutely right that in general:
|a-b| \neq |a|+|b|
Let me clarify with specific examples to show why the alternating sign pattern is crucial here:
Suppose we have:
Then:
x_{i+1} = x_{i-1} - x_i q_{i+1} = 5 - (-3 \times 2) = 5 + 6 = 11
And:
|x_{i+1}| = 11
|x_{i-1}| + q_{i+1}|x_i| = 5 + 2 \times 3 = 5 + 6 = 11
The key insight is that when x_{i-1} and x_i have opposite signs, and since q_{i+1} > 0, the subtraction in x_{i-1} - x_i q_{i+1} actually becomes addition of absolute values!
This happens because:
So we get:
|x_{i-1} - x_i q_{i+1}| = |x_{i-1} + |x_i q_{i+1}|| = |x_{i-1}| + q_{i+1}|x_i|
This is not just “eliminating minuses” but a mathematical consequence of the alternating sign pattern. The subtraction operation combined with the alternating signs creates a situation where absolute values add.
This is why proving the sign pattern (-1)^i x_i \leq 0 first is essential - it guarantees that consecutive terms in the sequence have opposite signs, creating this special case where the absolute value of their difference equals the sum of their absolute values.
Does this explanation help clarify the mathematical principle at work here?
Can you make it clear for me about “absolute numbers” behaviour? You that’s special case that we have to blindly memorize?
Ah, I see your question clearly now! Let me illuminate the principle of absolute values rather than presenting a rule to memorize blindly.
There is a fundamental property of absolute values that isn’t just a special case but follows from their definition:
For any real numbers a and b:
This isn’t a special case to memorize, but rather emerges from the definition of absolute value as the distance from zero.
Let me demonstrate with a concrete example:
Consider |5 - (-3)|:
In our extended Euclidean algorithm context, when we have x_{i+1} = x_{i-1} - x_i q_{i+1}, the terms x_{i-1} and x_i q_{i+1} have opposite signs (due to the alternating sign pattern we need to prove).
This means that the subtraction operation actually increases the absolute value, rather than decreasing it. It’s not about “switching signs” but about understanding how absolute values behave when operations are performed on numbers with different signs.
This is why proving the sign pattern (-1)^i x_i \leq 0 first is crucial - it establishes that we’re in this particular scenario where absolute values add up rather than subtract.
Does this clarify the mathematical reasoning? This is about understanding the nature of absolute values rather than memorizing a special case.
Indeed , that’s amazing! So both opposite and the same sign equals to |a|+|b|. Is it general thing??? Like any opposite signed |a-b|=|a|+|b|??? It doesn’t depend on a<b,a>b??
For any real numbers a and b:
If a and b have the SAME sign, then:
|a + b| = |a| + |b|
(This is true because adding two positive numbers gives a positive number, and adding two negative numbers gives a negative number whose absolute value equals the sum of the absolute values)
If a and b have OPPOSITE signs, then:
|a + b| = ||a| - |b||
(This equals the absolute difference between |a| and |b|)
For subtraction, |a - b|:
The user’s confusion is thinking that opposite signs always lead to |a - b| = |a| + |b| regardless of whether a > b or a < b. This is incorrect.
Let me provide some clear examples to clarify:
Example 1: |5 - 3| = |2| = 2, but |5| + |3| = 8
Example 2: |5 - (-3)| = |5 + 3| = |8| = 8, which equals |5| + |-3| = 5 + 3 = 8
Example 3: |-5 - 3| = |-8| = 8, which equals |-5| + |3| = 5 + 3 = 8
I need to make it clear that |a - b| = |a| + |b| is true ONLY when a and b have opposite signs.
No, my young philosopher, I need to correct a misunderstanding that has arisen! Let me clarify this important principle of absolute values:
For any real numbers a and b:
For the sum |a + b|:
For the difference |a - b|:
It is NOT universally true that |a - b| = |a| + |b|! This equality holds ONLY when a and b have opposite signs.
Let me demonstrate with examples:
Example 1: |5 - 3| = |2| = 2, but |5| + |3| = 8 (same signs, not equal)
Example 2: |5 - (-3)| = |5 + 3| = |8| = 8, which equals |5| + |-3| = 5 + 3 = 8 (opposite signs, equality holds)
Example 3: |3 - 5| = |-2| = 2, but |3| + |5| = 8 (same signs, not equal)
In our Extended Euclidean Algorithm context, the formula |x_{i+1}| = |x_{i-1}| + q_{i+1}|x_i| works specifically because we first establish that x_{i-1} and x_i have opposite signs, which is why we need to prove the alternating sign pattern first.
This principle is a fundamental property of absolute values based on their definition as distance from zero, not a special case to memorize without understanding.
