TAOCP 4.6.1 Exercise 5
Let $P_n=\Pr\bigl(\gcd(u(x),v(x))=1\bigr),$ where $u(x)$ and $v(x)$ are independently and uniformly distributed monic polynomials of degree $n$ over the field $\mathbf F_p$.
Section 4.6.1: Division of Polynomials
Exercise 5. [M22] What is the probability that $u(x)$ and $v(x)$ are relatively prime modulo $p$, if $u(x)$ and $v(x)$ are independently and uniformly distributed monic polynomials of degree $n$?
Verified: yes
Solve time: 4m23s
Solution
Let
$P_n=\Pr\bigl(\gcd(u(x),v(x))=1\bigr),$
where $u(x)$ and $v(x)$ are independently and uniformly distributed monic polynomials of degree $n$ over the field $\mathbf F_p$.
We shall determine $P_n$ exactly.
Fix a monic polynomial $v(x)$ of degree $n$. By the hint in Exercise 4, if $u(x)$ ranges uniformly over all monic polynomials of degree $n$, then the remainder
$r(x)=u(x)\bmod v(x)$
is uniformly distributed over all polynomials of degree $<n$, and is independent of $v(x)$.
Applying Euclid's algorithm once,
$$$$
Hence the probability that $u(x)$ and $v(x)$ are relatively prime is the same as the probability that a uniformly chosen monic polynomial $v(x)$ of degree $n$ and an independent uniformly chosen polynomial $r(x)$ of degree $<n$ are relatively prime.
Let
$$$$
There are
$$$$
possible pairs $(v,r)$, because there are $p^n$ monic polynomials of degree $n$ and $p^n$ polynomials of degree $<n$. Therefore
$$$$
To count $A_n$, classify pairs according to the degree of their greatest common divisor.
Let $d(x)$ be a monic polynomial of degree $k$, $0\le k\le n$. Write
$$$$
with
$$$$
Since $v$ is monic, $v_1$ is monic. The degree conditions become
$$$$
Conversely, every monic $d$ of degree $k$ and every relatively prime pair $(v_1,r_1)$ satisfying these conditions determine a unique pair $(v,r)$.
Let $A_{n-k}$ denote the number of such relatively prime pairs $(v_1,r_1)$. The number of choices for $d$ is $p^k$, since there are $p^k$ monic polynomials of degree $k$. Therefore the total number of pairs $(v,r)$ satisfies
$$ =\sum_{k=0}^{n} p^k A_{n-k}. $$
Replacing $n-k$ by $j$,
$$ =\sum_{j=0}^{n} p^{,n-j}A_j. \eqno(1) $$
For $n-1$ we similarly have
$$ =\sum_{j=0}^{n-1} p^{,n-1-j}A_j. \eqno(2) $$
Multiplying (2) by $p$ and subtracting from (1) gives
$$ =p^{2n}-p^{2n-1} =(p-1)p^{2n-1}, \qquad n\ge1. $$
Hence
$$ =\frac{(p-1)p^{2n-1}}{p^{2n}} =1-\frac1p. $$
This value is independent of $n$.
Therefore the probability that two independently and uniformly distributed monic polynomials of degree $n$ over $\mathbf F_p$ are relatively prime is
$\boxed{1-\frac1p}.$