Difference between revisions of "2020 USAMO Problems/Problem 3"
m (→Solution: newbox) |
(→Solution) |
||
Line 8: | Line 8: | ||
{{USAMO newbox|year=2020|num-b=2|num-a=4}} | {{USAMO newbox|year=2020|num-b=2|num-a=4}} | ||
+ | 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]: <math>p\equiv 3\pmod{4}</math>. Work in <math>\mathbb{F}_{p^2} = \mathbb{F}_p[i]</math>. Suppose <math>a\in A</math>. Then, <math>a=-x^2</math> for some <math>x\in\mathbb{F}_p</math> and <math>4-a=y^2</math> for some <math>y\in\mathbb{F}_p</math>, so we have <cmath>x^2+y^2 = -4.</cmath> This factors as <cmath>(x+iy)(x-iy) = (2i)^2,</cmath> so we have <math>x+iy=2it</math> and <math>x-iy=2i/t</math> for some <math>t\in\mathbb{F}_p[i]</math>, so <cmath>x=i(t+1/t)\quad\text{and}\quad y=t-1/t.</cmath> For both of these to be in <math>\mathbb{F}_p</math>, we need <math>x^p=x</math> and <math>y^p=y</math>, which when we work out with frobenius, tells us that <math>t^{p+1}+1=0</math>. | ||
+ | |||
+ | Thus, if <math>a\in A</math>, we must have <math>a=(t+1/t)^2</math> for some <math>t\in\mathbb{F}_p[i]</math> such that <math>t^{p+1}+1=0</math>. Actually it is easy to see that if <math>t</math> satisfies <math>t^{p+1}+1=0</math>, then both <math>a</math> and <math>4-a</math> are QNRs (just reverse the frobenius calculation above). Thus, <cmath>A = \{(t+1/t)^2 : t\in\mathbb{F}_p[i], t^{p+1}+1=0\}.</cmath> Note <math>(t+1/t)^2 = (t'+1/t')^2</math> if and only if <math>t'\in\{t,-t,1/t,-1/t\}</math>, and also <math>t^{p+1}+1=0\iff (t')^{p+1}+1=0</math>. Note that <cmath>t^{p+1}+1\mid t^{p^2}-t</cmath> as <math>2(p+1)\mid p^2-1</math>, so <math>t^{p+1}+1</math> has distinct roots in <math>\mathbb{F}_p[i]</math>. We see that <cmath>t^{p+1}+1=(t^{\frac{p+1}{2}}+i)(t^{\frac{p+1}{2}}-i),</cmath> and <math>s</math> a root of <math>t^{\frac{p+1}{2}}-i</math> if and only if <math>1/s</math> is a root. Thus, it is easy to see that <cmath>A = \{(t+1/t)^2 : t\in\mathbb{F}_p[i], t^{\frac{p+1}{2}}-i=0\}.</cmath> In this parameterization, only <math>t</math> and <math>-t</math> produce the same value (and these never coincide as <math>t\ne 0</math>), so we actually have <cmath>T:=\prod_{a\in A}=(-1)^{\frac{p+1}{4}}\prod_{\substack{t\in\mathbb{F}_p[i]\\t^{\frac{p+1}{2}}-i=0}}(t+1/t).</cmath> This becomes <cmath>T=(-1)^{\frac{p+1}{4}}\prod_{\substack{t\in\mathbb{F}_p[i]\\t^{\frac{p+1}{2}}-i=0}}\frac{(t+i)(t-i)}{t}.</cmath> Letting <math>f(x)=x^{\frac{p+1}{2}}-i</math>, we see that this product becomes <cmath>T=(-1)^{\frac{p+1}{4}}\frac{f(-i)f(i)}{f(0)}.</cmath> It is tedious but straightforward to see that this always gives <math>2</math>. | ||
+ | |||
+ | [b]Case 2[/b]: <math>p\equiv 1\pmod{4}</math>. Let <math>\ell</math> be some QNR mod <math>p</math> (sadly we don't have any free QNRs like <math>-1</math> is for <math>3\pmod{4}</math> primes). Let <math>\omega</math> be a formal square root of <math>\ell</math>, and work in <math>\mathbb{F}_{p^2} = \mathbb{F}_p[\omega]</math>. Then, if <math>a\in A</math>, we have <cmath>\omega^2 a = x^2\quad\text{and}\quad\omega^2(4-a)=y^2,</cmath> so <math>x^2+y^2=4\omega^2</math>, so factoring and doing the same as before, we get <cmath>x=\omega(t+1/t)\quad\text{and}\quad y=\frac{\omega}{i}(t-1/t)</cmath> for some <math>t\in\mathbb{F}_p[\omega]</math>. These are in <math>\mathbb{F}_p</math> if and only if <math>t^{p-1}+1=0</math> (using frobenius). We see <math>a=(t+1/t)^2</math>, so <cmath>A = \{(t+1/t)^2 : t\in\mathbb{F}_p[\omega], t^{p-1}+1=0\}.</cmath> Doing a similar analysis as before, the desired product becomes <cmath>T:=\prod_{a\in A}=(-1)^{\frac{p-1}{4}}\prod_{\substack{t\in\mathbb{F}_p[\omega]\\t^{\frac{p-1}{2}}-i=0}}\frac{(t+i)(t-i)}{t},</cmath> and letting <math>f(x)=x^{\frac{p-1}{2}}-i</math>, we get <cmath>T=(-1)^{\frac{p-1}{4}}\frac{f(-i)f(i)}{f(0)},</cmath> which again is always <math>2</math>. | ||
+ | |||
+ | So the answer is <math>\boxed{2}</math>. | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 13:27, 4 December 2024
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.