How can we find a solution $f\in \mathbb{F}_5[x]$ for the following non-linear congruence?
$ f\equiv 1\mod{x}+1,\ x\cdot f\equiv x+1\mod{x^2}+1,\ (x+1)\cdot f\equiv x+ 1\mod{x^3}+1 $
How can we find a solution $f\in \mathbb{F}_5[x]$ for the following non-linear congruence?
$ f\equiv 1\mod{x}+1,\ x\cdot f\equiv x+1\mod{x^2}+1,\ (x+1)\cdot f\equiv x+ 1\mod{x^3}+1 $
Copyright © 2021 JogjaFile Inc.
Hint First you need to find inverse of $x$ modulo $x^2+1$. Then use the Chinese Remainder Theorem idea.
For the inverses observe:
$$x^2+ 1 \equiv 0 \pmod{x^2+1,5} \implies x(4x) \equiv 1 \pmod{x^2+1,5}.$$
Thus the second congruence can be written as $$xf(x) \equiv x+1 \pmod{x^2+1} \implies \color{blue}{f(x) \equiv (4x)(x+1) \equiv 4x+1 \pmod{x^2+1,5}}.$$
Can you procced from here?