# sequence of remainders modulo 2?

Consider the expression $A(x)$ = $B(x)\cdot x + R(x)$, where $A(x)$, $B(x)$, $R(x)$ are polynomials and degree of $R$ is less than degree of $B$, so $R$ is the remainder of long dividing $A$ by $B$. The start point is the pair $(A, B)$, in the first step you will change this pair to ($B$, $A$ mod $B$), then in the second step to ($A$ mod $B$, $B$ mod ($A$ mod $B$), and so on (like in gcd) until the second element in the pair is $0$.

suppose the starting pair $A$, $B$ take $N$ steps to reach the point where the second element in the pair is $0$. the pair $A\%2$ and $B\%2$ also take $N$ steps, but what is exactly the reason that they take the same number of steps?

Note that $A\%2$ and $B\%2$ mean applying mod 2 to all coefficients in $A$ and $B$.

EDIT: A constraint exists where the leading element in $A$ and $B$ (the element with highest power) should have a coefficient of 1, and Degree of $A$ should be higher than Degree of $B$.

EDIT2: Also there is a constraint that the last pair (in the last step) be (1,0), like fibonacci polynomials.

• What A%2 and B%2 are? – Artur Riazanov Jan 17 '18 at 19:01
• applying mod 2 to all coefficients of A and B – Mohamed EL Tair Jan 17 '18 at 19:05
• Then this is not true for $A=2x^2$ and $B = 2x$, for example. – Artur Riazanov Jan 17 '18 at 19:06
• Sorry I have forgot to mention an important constraint, check the edit – Mohamed EL Tair Jan 17 '18 at 19:11

Even with your correction, this still isn't true. Obviously, the regular sequence can be taken mod 2 to provide a mod 2 version, so the mod 2 sequence cannot be any longer than the regular sequence. But it is possible that the mod 2 sequence can reach $0$ before the regular sequence. For example, we can take $A = x^2$ and $B = x + 2$. Then:

$$x^2 = (x + 2)(x - 2) + (4)\\x + 2 = (4)\left(\frac x4 + \frac 12\right) + (0)$$ While mod 2, we still have $A = x^2$, but $B = x$, so we just have $$x^2 = (x)(x) + 0$$

EDIT

With the newly added EDIT2 which specifies that $A, B$ must be such that the penultimate remainder is $1$. So you have a sequence of pairs $(A_1, B_1), (A_2, B_2), \dots, (A_n, B_n)$ with $A_1 = A, B_1 = B, A_n = 1, B_n = 0$, and for all $i, A_{i+1} = B_i$.

If you take each of the elements of this sequence modulo 2, then you get the equivalent modulo 2 sequence. However, $A_n \pmod 2 = 1$ and $B_n \pmod 2 = 0$. So the modulo 2 sequence cannot be any shorter or longer than the regular sequence.

• degree of $R$ must be less than degree of $B$ as $R$ is the long division remainder of $A$ by $B$ – Mohamed EL Tair Jan 18 '18 at 3:25
• and check EDIT2, sorry for forgetting about it also – Mohamed EL Tair Jan 18 '18 at 3:34
• Your EDIT2 condition makes the whole thing trivial. When you take the full sequence modulo 2, that $1$ remainder from the penultimate step will still remain a $1$, so the mod 2 sequence cannot be shorter than the original. I'll add an edit of my own. – Paul Sinclair Jan 18 '18 at 3:39
• I fixed my example (silly to have forgotten to add the second term to the first quotient). I also have added the promised edit. – Paul Sinclair Jan 18 '18 at 3:57
• Ok, we have reached a good point. But: for $1<=i<n$ we know that in the original sequence $B(i+1)$ = $A(i) mod B(i)$, and we know that in the mod sequence $B(i+1) = (A(i) mod 2) mod (B(i) mod 2)$, is it guaranteed that $B(i+1) mod 2$ (I mean by $B(i+1)$ here the one of the original sequence) equals $B(i+1) mod 2$ (I mean by $B(i+1)$ here the one of the mod sequence) ? – Mohamed EL Tair Jan 18 '18 at 4:53