Let $S$ be a system of polynomial equations over $\mathbb{F}\_q$. 


Assume that $S$ has a solution in $\overline{\mathbb{F}\_q}$. 


Denote by $k$ the minimal number such that $S$ has $\mathbb{F}\_{q^k}$-rational solution.


How large can be $k$ (depends on $q$, the number of equations of $S$ and its degrees)? 



Degree of a field extension with a rational solution
Let $f(x)$ be an irreducible polynomial in $\mathbb F\_q[x]$ of degree $d$. Then the smallest $k$ such that $f(x)$ has a root in $\mathbb F\_{q^k}$ is $k=d$. More generally, let $f\_i(x)$ be an irreducible polynomial in $\mathbb F\_q[x]$ of degree $d\_i$. Then for $S=\{f\_1(x\_1),\ldots,f\_r(x\_r)\}$, the smallest $k$ such that $S$ has a solution $(x\_1,\ldots,x\_r)\in\mathbb F\_{q^k}^r$ is $k=\text{LCM}(d\_1,\ldots,d\_r)$. So taking the $d\_i$ to be pairwise relatively prime gives $k=d\_1\cdots d\_r$. 


Are you assuming at least that there exists a solution over $\overline{\mathbb F}\_q$? 


