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?
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
(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.
Transcribed from the official solutions, pages 4–5. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.