Let p be a prime number and let k be a positive integer. Suppose that the numbers ai=ik+i for i=0,1,…,p−1 form a complete residue system modulo p. What is the set of possible remainders of a2 upon division by p?
Πρωτότυπο από το επίσημο PDF
Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Χρόνος σε αυτό το θέμα
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(proposed by Tigran Hakobyan, Yerevan State University, Armenia)
Hint: Consider i=0∏p−1(ik+i).
Solution. First observe that p=2 does not satisfy the condtion, so p must be an odd prime.
Lemma. If p>2 is a prime and Fp is the field containing p elements, then for any integer 1≤n<p one has the following equality in the field Fp
α∈Fp∗∏(1+αn)=⎩⎨⎧0,2n,if gcd(p−1,n)p−1 is evenotherwise
Proof. We may safely assume that n∣p−1 since it can be easily proved that the set of n-th powers of the elements of Fp∗ coincides with the set of gcd(p−1,n)-th powers of the same elements. Assume that t1,t2,...,tn are the roots of the polynomial tn+1∈Fp[x] in some extension of the field Fp. It follows that
where we define Φ(t)=∏α∈Fp∗(t−α)=tp−1−1. Therefore
α∈Fp∗∏(1+αn)=i=1∏n(tip−1−1)=i=1∏n((tin)np−1−1)=i=1∏n((−1)np−1−1)={0,2n,if np−1 is evenotherwise
Let us now get back to our problem. Suppose the numbers ik+i,0≤i≤p−1 form a complete residue system modulo p. It follows that
α∈Fp∗∏(αk+α)=α∈Fp∗∏α
so that ∏α∈Fp∗(αk−1+1)=1 in Fp. According to the Lemma, this means that 2k−1=1 in Fp, or equivalently, that 2k−1≡1(modp). Therefore a2=2k+2≡4(modp) so that the remainder of a2 upon division by p is either 4 when p>3 or is 1, when p=3.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 4–5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.