1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ degree of $R$ must be less than degree of $B$ as $R$ is the long division remainder of $A$ by $B$ $\endgroup$ – Mohamed EL Tair Jan 18 '18 at 3:25
  • $\begingroup$ and check EDIT2, sorry for forgetting about it also $\endgroup$ – Mohamed EL Tair Jan 18 '18 at 3:34
  • $\begingroup$ 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. $\endgroup$ – Paul Sinclair Jan 18 '18 at 3:39
  • $\begingroup$ I fixed my example (silly to have forgotten to add the second term to the first quotient). I also have added the promised edit. $\endgroup$ – Paul Sinclair Jan 18 '18 at 3:57
  • $\begingroup$ 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) ? $\endgroup$ – Mohamed EL Tair Jan 18 '18 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.