# Coprime polynomials.

Let f(x) be a nonzero polynomial. Show that there exists a polynomial g(x) with f(x) g(x) ≡ 1 (mod p(x)) if and only if gcd (f(x), p(x)) = 1.

What is this math question asking us to prove?

Is the problem asking to show that there exists a polynomial g(x) or does it want us the prove f(x) g(x) ≡ 1 (mod p(x)) if and only if gcd (f(x), p(x)) = 1. If it is asking us to prove "f(x) g(x) ≡ 1 (mod p(x)) if and only if gcd (f(x), p(x)) = 1" I can do the forward direction. I am not sure how to prove "if f(x) g(x) ≡ 1 (mod p(x)), then (f(x), p(x)) = 1".

## 2 Answers

$\Rightarrow$: If there exists a polynomial $g$ with $fg\equiv1\,\text{mod}\,p$, then, by the definition of congruence modulo $p$, we have that $fg-1=hp$, for some polynomial $h$, and, rewriting the last equation, we get $fg+(-h)p=1$, i.e, $(f,p)=1$.

$\Leftarrow$: If $(f,p)=1$, then $fg+hp=1$ for some polynomials $g$ and $h$. Rewriting the last equation, we get $fg-1=(-h)p$, which is equivalent to $fg\equiv1\,\text{mod}\,p$. So in this case, there exists a polynomial $g$ with $fg\equiv1\,\text{mod}\,p$.

You're given two polynomials: $f(x)$ and $p(x)$. This question asks you to prove the equivalence of the following two statements:

• $f(x) g(x) \equiv 1$ mod $p$ for some polynomial $g(x)$, and
• $\gcd(f(x), p(x)) = 1$

Note that you're not given a polynomial $g$ to begin with. You have to show that such a $g$ exists given the second statement is true.