uniolympiads English

IMC 2023, Ημέρα 1, Θέμα 4

Let pp be a prime number and let kk be a positive integer. Suppose that the numbers ai=ik+ia_i = i^k + i for i=0,1,…,p−1i = 0, 1, \dots, p-1 form a complete residue system modulo pp. What is the set of possible remainders of a2a_2 upon division by pp?

Πρωτότυπο από το επίσημο PDFLet p be a prime number and let k be a positive integer. Suppose that the numbers a i = i k + i for i = 0, 1, . . . , p − 1 form a complete residue system modulo p. What is the set of possible remainders of a 2 upon division by p?

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(proposed by Tigran Hakobyan, Yerevan State University, Armenia)

Hint: Consider ∏i=0p−1(ik+i)\displaystyle\prod_{i=0}^{p-1}(i^k + i).

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

Lemma. If p>2p > 2 is a prime and Fp\mathbb{F}_p is the field containing pp elements, then for any integer 1≤n<p1 \le n < p one has the following equality in the field Fp\mathbb{F}_p

∏α∈Fp∗(1+αn)={0,if p−1gcd⁡(p−1,n) is even2n,otherwise\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 n∣p−1n|p-1 since it can be easily proved that the set of nn-th powers of the elements of Fp∗\mathbb{F}_p^* coincides with the set of gcd⁡(p−1,n)\gcd(p-1,n)-th powers of the same elements. Assume that t1,t2,...,tnt_1, t_2, ..., t_n are the roots of the polynomial tn+1∈Fp[x]t^n + 1 \in \mathbb{F}_p[x] in some extension of the field Fp\mathbb{F}_p. It follows that

∏α∈Fp∗(1+αn)=∏α∈Fp∗∏i=1n(α−ti)=∏i=1n∏α∈Fp∗(α−ti)=∏i=1n∏α∈Fp∗(ti−α)=∏i=1nΦ(ti),\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 Φ(t)=∏α∈Fp∗(t−α)=tp−1−1\Phi(t) = \prod_{\alpha\in\mathbb{F}_p^*}(t-\alpha) = t^{p-1} - 1. Therefore
∏α∈Fp∗(1+αn)=∏i=1n(tip−1−1)=∏i=1n((tin)p−1n−1)=∏i=1n((−1)p−1n−1)={0,if p−1n is even2n,otherwise\prod_{\alpha\in\mathbb{F}_p^*}(1+\alpha^n) = \prod_{i=1}^{n}(t_i^{p-1} - 1) = \prod_{i=1}^{n}((t_i^n)^{\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 ik+i,0≤i≤p−1i^k + i, 0 \le i \le p-1 form a complete residue system modulo pp. It follows that

∏α∈Fp∗(αk+α)=∏α∈Fp∗α\prod_{\alpha\in\mathbb{F}_p^*}(\alpha^k + \alpha) = \prod_{\alpha\in\mathbb{F}_p^*}\alpha
so that ∏α∈Fp∗(αk−1+1)=1\prod_{\alpha\in\mathbb{F}_p^*}(\alpha^{k-1} + 1) = 1 in Fp\mathbb{F}_p. According to the Lemma, this means that 2k−1=12^{k-1} = 1 in Fp\mathbb{F}_p, or equivalently, that 2k−1≡1(mod p)2^{k-1} \equiv 1 (\mathrm{mod}\ p). Therefore a2=2k+2≡4(mod p)a_2 = 2^k + 2 \equiv 4 (\mathrm{mod}\ p) so that the remainder of a2a_2 upon division by pp is either 44 when p>3p > 3 or is 11, when p=3p = 3.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 4–5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;