0
$\begingroup$

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".

$\endgroup$
0
$\begingroup$

$\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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.