2020 USAMO Problems/Problem 3
Problem
Let be an odd prime. An integer
is called a quadratic non-residue if
does not divide
for any integer
.
Denote by the set of all integers
such that
, and both
and
are quadratic non-residues. Calculate the remainder when the product of the elements of
is divided by
.
Solution
This problem needs a solution. If you have a solution for it, please help us out by adding it.
2020 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
We will be using finite field theory and the Frobenius endomorphism freely. Also we will just give a sketch and leave out details like it's out of fashion.
[b]Case 1[/b]: . Work in
. Suppose
. Then,
for some
and
for some
, so we have
This factors as
so we have
and
for some
, so
For both of these to be in
, we need
and
, which when we work out with frobenius, tells us that
.
Thus, if , we must have
for some
such that
. Actually it is easy to see that if
satisfies
, then both
and
are QNRs (just reverse the frobenius calculation above). Thus,
Note
if and only if
, and also
. Note that
as
, so
has distinct roots in
. We see that
and
a root of
if and only if
is a root. Thus, it is easy to see that
In this parameterization, only
and
produce the same value (and these never coincide as
), so we actually have
This becomes
Letting
, we see that this product becomes
It is tedious but straightforward to see that this always gives
.
[b]Case 2[/b]: . Let
be some QNR mod
(sadly we don't have any free QNRs like
is for
primes). Let
be a formal square root of
, and work in
. Then, if
, we have
so
, so factoring and doing the same as before, we get
for some
. These are in
if and only if
(using frobenius). We see
, so
Doing a similar analysis as before, the desired product becomes
and letting
, we get
which again is always
.
So the answer is .
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.