Congruence modulo primes or in a polynomial ring over ${\rm GF}(2)$

Question

Let $p, q$ be primes. Then the linear congruence

$$ap \equiv r\pmod q$$

can be solved for $a\in\mathbb Z$ and will have a unique solution for each value of $r$ such that $0\leqslant a<q$.

Am I right about this?

That brings me to my main question.

Can I apply this result for polynomial ring over ${\rm GF}(2)$ and $2$ primitive polynomials instead of $p,q$?

Consider a polynomial ring $K[X]$ over ${\rm GF}(2)$ of order $n$ and $2$ primitive polynomials $P_1$ and $P_2$ with degrees $a$ and $b$ such that $a+b=n$. Let $y$ be an arbitrary polynomial, then does the equation

$$xP_1 \equiv y\pmod{P_2}$$

always have a solution for $x\in K[X]$ and $\deg(x)\leqslant b$?

I am not a math student, so please let me know if I am saying something incorrectly or if the question is not clear.

Answer 1

No, you are not right for the case $p=q$. Then $p \equiv 0 \pmod q$ and the solution is not unique.

Excluding this case, the proof of your statement is very simple. Because $p$ and $q$ are different prime numbers, $q$ does not divide $p$ and hence $p \not\equiv 0 \pmod q$ and $(\mathbb{Z}/q\mathbb{Z})^{*}=(\mathbb{Z}/q\mathbb{Z}) \setminus \{\bar{0}\}$. That means $p$ is invertible and therefore the endomorphism $x \mapsto p \cdot x$ is injective. After we know that every incective endomorphism of a finite group is even surjective, we can find for every $y \in (\mathbb{Z}/q\mathbb{Z})^{*}$ an unique element $x \in (\mathbb{Z}/q\mathbb{Z})^{*}$ such that $px \equiv y \pmod q$.

The case of $\mathbb{F}_{2}[X]$ ($\mathbb{F}_{2}$ is another notation for $\operatorname{GF}(2)$) instead of $\mathbb{Z}$ is very similar to that.

Let $p$ and $q$ be different prime polynoms in $\mathbb{F}_{2}[X]$. $\mathbb{F}_{2}[X]/q\mathbb{F}_{2}[X]$ is a field since q is prime in the euclidean ring $\mathbb{F}_{2}[X]$ (we know that in such a ring irreducible and prime elements are always the same and the quotient ring after a maximal ideal is a field) and $(\mathbb{F}_{2}[X]/q\mathbb{F}_{2}[X])^{*}=(\mathbb{F}_{2}[X]/q\mathbb{F}_{2}[X]) \setminus \{0\}$. Because $p$ is irreducible we observe that $p \not\equiv 0 \pmod q$, analogous to the $\mathbb{Z}$-case. Also note that this field is finite and hence we are allowed to use the same argument as above.

I hope it helped you a little bit to answer the question.

Answer 2

If $P_1$ and $P_2$ have a common factor $P$, then the answer is no: take any $y$ not divisible by $P$.

Thus assume $P_1, P_2$ have no common factor. Since $A = \mathbb{F}_2[X]$ is a principal ideal domain, the sum $(P_1) + (P_2) = A$. Thus we can write any $y\in A$ as $y = x P_1 + x' P_2$ for $x, x'\in A$. That gives $y\equiv x P_1\pmod{P_2}$, but it's not necessarily the case that we can take $\deg x\leq \deg P_2 - \deg P_1$. For example, take $P_1 = X^2 + X + 1$ and $P_2 = X^3 + X + 1$. For $y = X^3 + X^2 + 1$, it's easy to verify that $P_1 x\not\equiv y\pmod{P_2}$ for the four polynomials in $x\in A$ of degree at most $1$.