Multiplicative Inverses of Cong. Classes of Polys. Mod. p(x) over a Field

Multiplicative Inverses of Congruence Classes of Polynomials Modulo p(x) over a Field

Recall from the Congruence Classes of Polynomials Modulo p(x) over a Field page that if $(F, +, \cdot)$ is a field and $p \in F[x]$ then for any $a \in F[x]$ we defined the congruence class of $a$ modulo $p$ to be:

(1)

\begin{align} \quad [a(x)]_{p(x)} = \{ b(x) \in F[x] : b(x) \equiv a(x) \pmod {p(x)} \} \end{align}

We defined the set of all congruence classes modulo $p$ by $F[x] / <p(x)>$.

We will now show that a congruence class $[a(x)]_{p(x)} \in F[x] / <p(x)>$ has a multiplicative inverse if and only if $a$ and $p$ are relatively prime.

Theorem 1: Let $(F, +, \cdot)$ be a field and let $p \in F[x]$ with $p(x) \neq 0$. Then for any $a \in F[x]$, the congruence class $[a(x)]_{p(x)}$ has a multiplicative inverse in $F[x]/<p(x)>$ if and only if $\gcd (a, p) = 1$.

• Proof: Consider the following congruence:

(2)

\begin{align} \quad a(x)b(x) \equiv 1 \pmod {p(x)} \end{align}

• This congruence holds if and only if there exists a polynomial $q \in F[x]$ such that:

(3)

\begin{align} \quad p(x)q(x) = a(x)b(x) - 1 \quad \Leftrightarrow \quad 1 = a(x)b(x) + (-q(x))p(x) \end{align}

• But this holds if and only if $\gcd (a, p) = 1$. Hence $[a(x)]_{p(x)}$ has a multiplicative inverse $[b(x)]_{p(x)}$ in $F[x] / <p(x)>$ if and only if $\gcd (a, p) = 1$. $\blacksquare$