International Mathematics Competition
for University Students
2023

IMC2023: Day 1, Problem 4

Problem 4. Let \(\displaystyle p\) be a prime number and let \(\displaystyle k\) be a positive integer. Suppose that the numbers \(\displaystyle a_i=i^k+i\) for \(\displaystyle i=0,1,\ldots,p-1\) form a complete residue system modulo \(\displaystyle p\). What is the set of possible remainders of \(\displaystyle a_2\) upon division by \(\displaystyle p\)?

Tigran Hakobyan, Yerevan State University, Armenia

Solution. First observe that \(\displaystyle p=2\) does not satisfy the condtion, so \(\displaystyle p\) must be an odd prime.

Lemma. If \(\displaystyle p>2\) is a prime and \(\displaystyle \mathbb{F}_p\) is the field containing \(\displaystyle p\) elements, then for any integer \(\displaystyle 1\leq n<p\) one has the following equality in the field \(\displaystyle \mathbb{F}_p\)

\(\displaystyle \prod_{\alpha\in\mathbb{F}^*_p}(1+\alpha^n)= \begin{cases} 0,& \text{if} \ \dfrac{p-1}{\gcd(p-1,n)} \ \text{is even} \\ 2^n,& \text{otherwise} \\ \end{cases} \)

Proof. We may safely assume that \(\displaystyle n|p-1\) since it can be easily proved that the set of \(\displaystyle n\)-th powers of the elements of \(\displaystyle \mathbb{F}^*_p\) coincides with the set of \(\displaystyle \gcd(p-1,n)\)-th powers of the same elements. Assume that \(\displaystyle t_1,t_2,...,t_n\) are the roots of the polynomial \(\displaystyle t^n+1 \in\mathbb{F}_p[x]\) in some extension of the field \(\displaystyle \mathbb{F}_p\). It follows that

\(\displaystyle \prod_{\alpha\in\mathbb{F}^*_p}(1+\alpha^n)=\prod_{\alpha\in\mathbb{F}^*_p}\prod_{i=1}^n(\alpha-t_i)=\prod_{i=1}^n \prod_{\alpha\in\mathbb{F}^*_p}(\alpha-t_i)=\prod_{i=1}^n \prod_{\alpha\in\mathbb{F}^*_p}(t_i-\alpha)=\prod_{i=1}^n \Phi(t_i),\)

where we define \(\displaystyle \Phi(t)=\prod_{\alpha\in\mathbb{F}^*_p}(t-\alpha)=t^{p-1}-1\). Therefore

\(\displaystyle \prod_{\alpha\in\mathbb{F}^*_p}(1+\alpha^n)=\prod_{i=1}^n(t^{p-1}_i-1)=\prod_{i=1}^n((t^n_i)^{\frac{p-1}{n}}-1)=\prod_{i=1}^n((-1)^{\frac{p-1}{n}}-1)= \begin{cases} 0,& \text{if} \ \frac{p-1}{n} \ \text{is even} \\ 2^n,& \text{otherwise} \\ \end{cases} \)

Let us now get back to our problem. Suppose the numbers \(\displaystyle i^k+i, 0\leq i\leq p-1\) form a complete residue system modulo \(\displaystyle p\). It follows that

\(\displaystyle \prod_{\alpha\in\mathbb{F}^*_p}(\alpha^k+\alpha)=\prod_{\alpha\in\mathbb{F}^*_p}\alpha\)

so that \(\displaystyle \prod_{\alpha\in\mathbb{F}^*_p}(\alpha^{k-1}+1)=1\) in \(\displaystyle \mathbb{F}_p\). According to the Lemma, this means that \(\displaystyle 2^{k-1}=1\) in \(\displaystyle \mathbb{F}_p\), or equivalently, that \(\displaystyle 2^{k-1}\equiv 1(\text{mod}\ p)\). Therefore \(\displaystyle a_2=2^k+2\equiv 4(\text{mod} \ p)\) so that the remainder of \(\displaystyle a_2\) upon division by \(\displaystyle p\) is either 4 when \(\displaystyle p>3\) or is 1, when \(\displaystyle p=3\).