Difference between revisions of "2020 USAMO Problems/Problem 3"

(create boilerplate)
 
(Solution)
 
(One intermediate revision by one other user not shown)
Line 7: Line 7:
 
{{Solution}}
 
{{Solution}}
  
{{USAMO box|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 $p$ be an odd prime. An integer $x$ is called a quadratic non-residue if $p$ does not divide $x - t^2$ for any integer $t$.

Denote by $A$ the set of all integers $a$ such that $1 \le a < p$, and both $a$ and $4 - a$ are quadratic non-residues. Calculate the remainder when the product of the elements of $A$ is divided by $p$.

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

2020 USAMO (ProblemsResources)
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]: $p\equiv 3\pmod{4}$. Work in $\mathbb{F}_{p^2} = \mathbb{F}_p[i]$. Suppose $a\in A$. Then, $a=-x^2$ for some $x\in\mathbb{F}_p$ and $4-a=y^2$ for some $y\in\mathbb{F}_p$, so we have \[x^2+y^2 = -4.\] This factors as \[(x+iy)(x-iy) = (2i)^2,\] so we have $x+iy=2it$ and $x-iy=2i/t$ for some $t\in\mathbb{F}_p[i]$, so \[x=i(t+1/t)\quad\text{and}\quad y=t-1/t.\] For both of these to be in $\mathbb{F}_p$, we need $x^p=x$ and $y^p=y$, which when we work out with frobenius, tells us that $t^{p+1}+1=0$.

Thus, if $a\in A$, we must have $a=(t+1/t)^2$ for some $t\in\mathbb{F}_p[i]$ such that $t^{p+1}+1=0$. Actually it is easy to see that if $t$ satisfies $t^{p+1}+1=0$, then both $a$ and $4-a$ are QNRs (just reverse the frobenius calculation above). Thus, \[A = \{(t+1/t)^2 : t\in\mathbb{F}_p[i], t^{p+1}+1=0\}.\] Note $(t+1/t)^2 = (t'+1/t')^2$ if and only if $t'\in\{t,-t,1/t,-1/t\}$, and also $t^{p+1}+1=0\iff (t')^{p+1}+1=0$. Note that \[t^{p+1}+1\mid t^{p^2}-t\] as $2(p+1)\mid p^2-1$, so $t^{p+1}+1$ has distinct roots in $\mathbb{F}_p[i]$. We see that \[t^{p+1}+1=(t^{\frac{p+1}{2}}+i)(t^{\frac{p+1}{2}}-i),\] and $s$ a root of $t^{\frac{p+1}{2}}-i$ if and only if $1/s$ is a root. Thus, it is easy to see that \[A = \{(t+1/t)^2 : t\in\mathbb{F}_p[i], t^{\frac{p+1}{2}}-i=0\}.\] In this parameterization, only $t$ and $-t$ produce the same value (and these never coincide as $t\ne 0$), so we actually have \[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).\] This becomes \[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}.\] Letting $f(x)=x^{\frac{p+1}{2}}-i$, we see that this product becomes \[T=(-1)^{\frac{p+1}{4}}\frac{f(-i)f(i)}{f(0)}.\] It is tedious but straightforward to see that this always gives $2$.

[b]Case 2[/b]: $p\equiv 1\pmod{4}$. Let $\ell$ be some QNR mod $p$ (sadly we don't have any free QNRs like $-1$ is for $3\pmod{4}$ primes). Let $\omega$ be a formal square root of $\ell$, and work in $\mathbb{F}_{p^2} = \mathbb{F}_p[\omega]$. Then, if $a\in A$, we have \[\omega^2 a = x^2\quad\text{and}\quad\omega^2(4-a)=y^2,\] so $x^2+y^2=4\omega^2$, so factoring and doing the same as before, we get \[x=\omega(t+1/t)\quad\text{and}\quad y=\frac{\omega}{i}(t-1/t)\] for some $t\in\mathbb{F}_p[\omega]$. These are in $\mathbb{F}_p$ if and only if $t^{p-1}+1=0$ (using frobenius). We see $a=(t+1/t)^2$, so \[A = \{(t+1/t)^2 : t\in\mathbb{F}_p[\omega], t^{p-1}+1=0\}.\] Doing a similar analysis as before, the desired product becomes \[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},\] and letting $f(x)=x^{\frac{p-1}{2}}-i$, we get \[T=(-1)^{\frac{p-1}{4}}\frac{f(-i)f(i)}{f(0)},\] which again is always $2$.

So the answer is $\boxed{2}$. The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png