If a polynomial $f(x)$, of degree at least four, is such that $$f(x) \equiv 3x+1 \mod (x^{2}-1)$$ and $$f(x) \equiv 2x-3\mod (x^{2}+1),$$ find the remainder $g(x)$ such that $$f(x) \equiv g(x) \mod (x^{2}-1)(x^{2}+1).$$
Asked
Active
Viewed 62 times
2
-
1Do you know the Chinese Remainder Theorem? – quid Feb 08 '15 at 15:00
-
@quid: Thanks. I am aware of the name but not of the thing under the name. Thanks for a clue. I am checking that, which is not a part of my working knowledge :) – Yes Feb 08 '15 at 15:03
-
@quid: Would you like to write up a proof, even a sketch if time does not allow. – Yes Feb 08 '15 at 15:06
-
I wrote something. Double check the calculations though; the method is definitely sound. I am a rubbish-computer with such things. – quid Feb 08 '15 at 15:26
1 Answers
2
The main steps are:
We note that $\frac{1}{2} (x^2 + 1) - \frac{1}{2} (x^2 - 1) = 1$.
Thus the inverse of $x^2 + 1 \mod x^2 -1$ is $1/2$ and the inverse of $x^2 - 1 \mod x^2 +1$ is $-1/2$.
Thus a solution is $(3x+ 1) \frac{x^2 + 1}{2} + (2x-3) (-\frac{x^2 - 1}{2}) $.
The first step can be done in a more systematic way using the extended Euclidean algorithm. The general method is the Chinese Remainder Theorem for polynomials.
quid
- 42,135
-
-
1A modular inverse of $a \mod b$ is an element $c$ such that $ac $ is $1$ $\mod b$. Observe that $\frac{1}{2} (x^2 + 1) = 1 + \frac{1}{2}(x^2 - 1)$ so $\frac{1}{2} (x^2 + 1)$ is $1$ mod $x^2 - 1$ – quid Feb 08 '15 at 15:39
-
Pardon me. I do not see a way to go from the second to the third. Does it have something to do with the Chinese Remainder Theorem? Appreciated. – Yes Feb 08 '15 at 15:44
-
1Yes it does;see the page I linked. Howver to see it directly jjust note that $a \frac{x^2 + 1}{2} + b (-\frac{x^2 - 1}{2}) $ is $a$ mod $x^2 - 1 $ and $b$ mod $x^2 + 1$ as $\frac{x^2 + 1}{2}$ is then $1$ and $0$ respectively and conversely for $-\frac{x^2 - 1}{2}$ . – quid Feb 08 '15 at 15:52
-