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.