Quadratic residues in a given interval

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Quadratic residues in a given interval

G H J

Reveal topic tags

modular arithmetic

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

Source: Brazilian Math Olympiad, Problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

236 posts

#1 h Nov 2, 2007, 1:50 AM • 2 Y

Y by Davi-8191, Adventure10

Find the number of integers $c$ such that $-2007 \leq c \leq 2007$ and there exists an integer $x$ such that $x^2 + c$ is a multiple of $2^{2007}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1313 posts

TTsphn

#2 h Nov 2, 2007, 2:56 AM • 2 Y

Y by Adventure10, Mango247

Consider the quadric :
$x^2\equiv c (\mod 2^k)$ where $c \equiv 1 (\mod 2)$
If $k\geq 3$ then the equation has solution if and only if :
$c\equiv 1 (\mod 8)$
You can prove by induction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

428 posts

#3 h Nov 2, 2007, 12:48 PM • 2 Y

Y by Adventure10, Mango247

Clearly, $c=0$ fulfills the property, so let $c$ non-zero from now on. Write a candidate as $c=2^{n}m$ with $0\leq n$ and an odd $m\in\mathbb{Z}$ . From $|c|\leq 2007$ we get $n\leq 10$ and from $x^2\equiv-c\bmod{2^{2007}}$ we get $n$ even, i.e. $c=2^{2t}m$ with $0\leq t\leq 5$ and $|m|\leq\frac{2007}{2^{2t}}$ . Therefore, we have $y^2=-m\bmod{2^{2007-2t}}$ with $y=\frac{x}{2^t}$ odd.

In general, we observe $(1+2x)^2=1+4x(x+1)\equiv 1\bmod{8}$ and for $k\geq 3$ we have ${ ((\mathbb{Z}/2^k\mathbb{Z}})^*)^2\simeq ((\mathbb{Z}/2\mathbb{Z})\times (\mathbb{Z}/2^{k-2}\mathbb{Z}))^2\simeq \mathbb{Z}/2^{k-3}\mathbb{Z}$ , i.e. $y^2\equiv -m\bmod{2^{2007-2t}}\Longleftrightarrow m\equiv -1\bmod{8}$ and the solution set is

$\{-1+8r|-250\leq r\leq 251\}\cup\\ \{-4+32r|-62\leq r\leq 62\}\cup\\ \{-16+128r|-15\leq r\leq 15\}\cup\\ \{-64+512r|-3\leq r\leq 4\}\cup\\ \{0,-256,-256+2048,-1024\}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#4 h Nov 3, 2007, 1:04 PM • 2 Y

Y by Adventure10, Mango247

Counting all the solutions, we discover that there are $669$ solutions (if I'm not wrong). This number is exactely $2007/3$ . Is there a simple way to discover that the answer is $2007/3$ ? Well, if we consider $n=2007$ and we make $n\longrightarrow \infty$ , I think the number of solutions tend to $\frac{1}{8}\cdot 2\cdot n(1+\frac{1}{4}+\frac{1}{16}+\frac{1}{64}+\cdots )=\frac{n}{3}$ . Is this correct?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

236 posts

#5 h Nov 3, 2007, 3:35 PM • 1 Y

Y by Adventure10

If I'm not mistaken, the answer is $670$ . But you're right about it being roughly $n/3$ .

I'm curious about the general case, i.e., what are the $p$ -th power residues ${}\bmod p^m$ ? That is, what are the numbers $0\leq c < p^m$ such that the congruence $x^p \equiv c \pmod{p^m}$ has solution?

I know how to solve it for $p = 3$ . I didn't think about the other cases, though.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

761 posts

#6 h Oct 10, 2011, 5:31 AM • 2 Y

Y by Adventure10, Mango247

the general result:
$x^2$ can be congruent to any number congurent to $1$ modulo $8$ .
it's not difficult to prove,by induction on $k$ ,where the modulo is $2^k$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#7 h Mar 24, 2021, 2:51 PM • 4 Y

Y by Mango247, Mango247, Mango247, endless_abyss

Lemma: Mod $2^n$ , an odd number is a quadratic residue if and only if it is $\equiv 1 \pmod{8}$ ,
Proof: Firstly, this is necessary because $(2k+1)^2 = 4k(k+1)+1 \equiv 1 \pmod{8}$ .

This is sufficient as well, we will show that there are at least $2^{n-3}$ distinct odd quadratic residues. Consider odds $x,y < 2^{n-2}$ . I claim that $x^2\equiv y^2 \pmod{2^{n}} \Longrightarrow x\equiv y \pmod{2^n}$ .

Consider two cases:

Case 1, $v_2(x-y)=1$ ,
$v_2(x^2-y^2) = v_2(x-y)+v_2(x+y) < 1 + (n-1) = n, \text{ a fail }$ Case 2, $v_2(x+y)=1$ , then we have $v_2(x-y)\geq n-1$ , and $y-x < 2^{n-2} \Longrightarrow y\equiv x \pmod{2^n}$ .

Since there are $2^{n-3}$ odds less than $2^{n-2}$ , we are done $\square$ .

We now answer extract.

Case 1: For odd c, we choose one of the 502 values
$-2007,-1999,\ldots 1993, 2001$
Case 2: For $2\mid x \Longrightarrow 4\mid x$ , we scale down the range to [-501,501]. We then choose one of the 125 from
$-495, -487, \ldots 489, 497$
Case 3: For $4\mid x \Longrightarrow 16\mid x$ , we scale down the c-range to [-125,125] and choose of the 31 values.
$-119,-111,\ldots 113,121$
Case 4: For $8\mid x \Longrightarrow 64\mid x$ , we scale down the c-range to [-31,31]. From here we can choose any of 8 choices
$-31, -23,-15,-7,1,9,17,25$ Next scale down brings us to [-7,7], from here we can choose four values, -7, 0,1,4.

Thus, in total we have 502+125+31+8+4=670 values of $c$ that work.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#8 h Aug 30, 2021, 3:18 PM

Y by

The key claim is the following characterization of quadratic residues modulo $2^n$ :

Claim: For $n \geq 3$ , if $\nu_2(a)\leq n-3$ , $a$ is a nonzero quadratic residue modulo $2^n$ if and only if $\tfrac{a}{\nu_2(a)} \equiv 1 \pmod{8}$ and $\nu_2(a)$ is even.
Proof: I will first prove that if $a$ is odd, then $a$ is a quadratic residue modulo $2^n$ if and only if $a \equiv 1 \pmod{8}$ . Note that if $a$ is a quadratic residue modulo $2^n$ for $n\geq 3$ , it must be a quadratic residue modulo $8$ as well, so any odd quadratic residues mod $2^n$ must be 1 mod $8$ . Thus, we only have to prove that every $a \equiv 1 \pmod{8}$ works. This is by induction on $n$ , with the base case of $n=3$ being obvious.
I will prove that if $a$ is an odd quadratic residue $\pmod{2^n}$ , then both $a$ and $a+2^n$ are quadratic residues $\pmod{2^{n+1}}$ . Pick $x$ such that $x^2 \equiv a \pmod{2^n}$ . Then mod $2^n$ , we have $(2^{n-1}+x)^2 \equiv a \pmod{2^n}$ , but $(2^{n-1}+x)^2 \not \equiv x^2 \pmod{2^{n+1}}$ . Thus one of $x^2,(2^{n-1}+x)^2$ is $a$ mod $2^{n+1}$ , and the other is $a+2^n$ .
Now suppose $2^{k}b$ is a quadratic residue mod $2^n$ . Clearly $k$ is even, so pick $y$ such that $(2^{k/2}y)^2 \equiv b \pmod{2^n}$ , where $b$ is odd (and therefore $y$ is odd). Then $y^2 \equiv b \pmod{2^{n-k}}$ . We have that $b$ is odd and $k \leq n-3$ , $n-k \geq 3$ , hence by the above result we require $b\equiv 1 \pmod{8}$ . $\blacksquare$

It remains to perform the answer extraction, which we will do by considering $\nu_2(a)$ . Letting $f(n)$ denote the number of integers in $[-n,n]$ which are $1 \pmod{8}$ , we can find that the answer is $f(2007)+f(501)+f(125)+f(31)+f(7)+f(2)+1$ , where the $+1$ at the end corresponds to $0$ working. It is easy to compute this quantity as $670$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8866 posts

#9 h Apr 8, 2023, 10:51 PM • 1 Y

Y by Funcshun840

The key claim is the following:

Claim. All $a \equiv 1 \pmod 8$ are the only odd quadratic residues mod $2^n$ for any $n \geq 3$ .

Proof. Obviously the condition is restrictive. To show that they all work, it suffices to show that there are $2^{n-3}$ quadratic residues mod $2^n$ . But observe that the order of $5$ mod $2^n$ is $2^{n-2}$ by a simple LTE computation. Hence, all powers of this quasi-generator $5^{2a}$ for $0 \leq a < 2^{n-3}$ are distinct quadratic residues, which suffices. $\blacksquare$

Now for obvious reasons, $n$ is a quadratic residue if and only if $n = 2^k \cdot n'$ for $n' \equiv 1 \pmod 8$ and $k$ even. A computation yields the number of such numbers as $670$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3371 posts

#10 h Aug 2, 2023, 6:46 PM

Y by

The problem is simply finding all QR's in between $-2007$ and $2007$ . It suffices to find only the odds, because then we can just add an even power of $2$ . We will prove that a odd number is a QR iff it is 1 $\pmod 8$ using induction. Notice that an odd QR must be $1 \pmod 8$ . Assume that this is true for $2^n$ . If $a$ is a QR $\pmod{2^n}$ , let $x^2 \equiv a \pmod{2^n}$ . This implies that $x^2 = a, a+2^n \pmod{2^{n+1}}$ . Notice we only have to worry about the latter case. Assume that $x^2 = a+2^n$ . Notice that now $(2^{n-1} - x)^2 = x^2 \pmod{2^n}$ . If $(2^{n-1}-x)^2 = a \pmod{2^{n+1}}$ , we are done with the induction. If $(2^{n-1}-x)^2 = a+2^n \pmod{2^{n+1}}$ which implies that $x$ is even, which is a contradiction. Now we know the answer is all numbers where the odd part is $1 \pmod 8$ . The answer readily follows.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1292 posts

#11 h Sep 2, 2023, 5:29 AM

Y by

Used 30% hint

It suffices to find the # of QR from -2007 to 2007 mod 2^2007. The key is to see that alll $a \equiv 1 \pmod 8$ are the only odd QR mod 2^n; this follows from knowing 1 mod 8 being the upper bound, and to show there are 2^{n-3} of these such QR, from computing using LTE, ord_{2^n}5=2^{n-2} this implies 5^{2k} has distinct QRs for $k\in[0,2^{n-3})\in\mathbb{Z}$ , since if there were two equal values the sequence would be periodic, but any periodic sequence must go over 1, and yet 1 hasn't occurred yet, meaning they're distinct QRs.
It follows that n is a QR iff $n=2^{2i}j$ for $j\equiv1\pmod8$ as the general answer; in particular, computation gives the answer of 670.

Remark. This is indeed generalizable by the technique we used.

This post has been edited 2 times. Last edited by huashiliao2020, Sep 2, 2023, 5:31 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4188 posts

#12 h Sep 28, 2023, 5:04 PM

Y by

Claim: For $n\geq 3$ , an odd positive integer $0\leq r\leq 2^n-1$ is a quadratic residue if and only if $r$ is 1 mod 8. The only if direction is trivial since the only odd quadratic residue mod 8 is 1.

For the other direction, use induction. This is clearly true for $n$ up to 4. Then, suppose that $8a+1\equiv k^2\pmod{2^n}$ We claim that we either have $8a+1\equiv k^2\pmod{2^{n+1}}$ or $8a+1\equiv (2^{n-1}-k)^2\pmod{2^{n+1}}.$ Suppose that the first condition is NOT true. Then, we must have $k^2\equiv 2^{n}+8a+1\pmod{2^{n+1}}.$ Thus, $(2^{n-1}-k)^2\equiv 2^{2n-2}-k2^n+k^2$ $\equiv 8a+1+2^n(1-k).$ Since $k$ is odd, this is just $8a+1$ mod $2^{n+1}$ , hence proven.

Claim 2: Suppose that $1\leq r\leq 2^n-1$ is an even residue mod $n$ . Then, $r$ is a quadratic residue if and only if the $v_2$ of $r$ is odd and the largest odd divisor of $r$ is a quadratic residue. Clearly, the $v_2$ being odd is necessary.

Let $r=2^{2k}q$ , so $q$ is the odd part. Since $r$ and $q$ differ by a square factor, one is a quadratic residue if and only if the other is, hence shown.

Thus, the answer is simply 0 in addition to any residues whose $v_2$ is even and odd part is 1 mod 8. The answer is then $670.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1327 posts

#13 h Oct 15, 2023, 4:08 PM

Y by

This question is basically asking for the number of quadratic residues $2^{2007}$ that are between $-2007$ and $2007$ .

Claim: A number is an odd QR of $2^n$ if and only if it is $\equiv 1\pmod{8}$ .

Taking the square of $(2k + 1)$ we get $(4k(k + 1)) + 1$ which is obviously always $1\pmod{8}$ .

Now to prove that all numbers $1\pmod{8}$ work, we can prove that there at least $2^{n-3}$ QRs $\pmod{2^n}$ .

Since the order of $5\pmod{2^n}$ is $2^{n-2}$ by LTE, there are $2^{n-3}$ odd QRs that take the form $5^{2a}\pmod{2^{n}}$ .

It is clear from here that all quadratic residues take the form $2^k$ multiplied by some number $1\pmod{8}$ , or is equal to $0$ .

Doing casework on $k$ , there are $502 + 125 + 31 + 8 + 3 + 1 = 670$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1745 posts

OronSH

#14 h Dec 3, 2023, 1:41 AM

Y by

First, if $c$ is odd then we will show that everything that works is $c \equiv -1 \pmod 8.$ Suppose $a^2 \equiv b^2 \pmod{2^{2007}}$ with $a,b$ odd. Then $(a+b)(a-b) \equiv 0 \pmod{2^{2007}},$ and since one of $a+b,a-b$ is $2 \pmod{4}$ we have either $a \equiv \pm b \pmod{2^{2006}}.$ Thus, all odds from $1$ to $2^{2005}-1$ have distinct residues, so there are at least $2^{2004}.$ However, notice that $a^2 \equiv 1 \pmod{8},$ so these $2^{2004}$ residues must precisely be the ones that are $1 \pmod{8}.$ Thus, we get that if $c$ is odd we have $x^2 \equiv -c \pmod{2^{2007}},$ so $c \equiv -1 \pmod 8$ and clearly these must all work.

Next if $c$ is even then we have $4 \mid c$ since we must have $4 \mid x^2.$ Then, letting $c_1=\frac c4$ and $x_1=\frac x2$ we get $2^{2005} \mid x_1^2+c_1.$ If $c_1$ is odd, then our argument from above still works since $2^{2005}$ is large enough, and if not, we just repeat this part.

Now for the answer extraction, we count the number of $c \equiv -1 \pmod 8$ from $-2007$ to $2007,$ then from $-501$ to $501,$ then from $-125$ to $125,$ then from $-31$ to $31,$ then from $-7$ to $7,$ then from $-1$ to $1,$ and finally add $1$ for $0.$ We get $502+125+31+8+2+1+1=670$ is the answer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

682 posts

#15 h Dec 26, 2023, 5:54 AM

Y by

Hard.

The question is asking for how QR behave modulo $2^n$ . The key idea is to notice that even and odd $x$ behave differently, and hence it makes sense to split into cases.

Claim: For odd $x$ , if $x^2 \equiv c \pmod{2^n}$ , then we have $c \equiv 1 \pmod{8}$ .

Proof. Proceed with induction. The base cases of $k = \{1, 2, 3, 4\}$ are easily managed. Then assume the induction holds till some $n = k -1$ . Then take some odd $x$ . We are given that $x^2$ modulo $2^{k-1}$ , is congruent to $1$ modulo $8$ . Clearly then modulo $2^k$ we have $x^2$ leaves a residue of the form $(x^2 \text{ modulo } 2^{k-1}) + m2^{k-1}$ for some $m$ . Now taking modulo $8$ we reach the claimed conclusion. $\blacksquare$

Thus we must necessarily have all QRs congruent to $1$ modulo $8$ .

Claim: All $c$ congruent to $1$ modulo $8$ are QRs modulo $2^n$ .

Proof. There are $2^{n-3}$ such $c$ . It suffices to show that there are at least $2^{n-3}$ QRs generated by odd $x$ , implying the claim. To see that this must hold note that we can take $5$ as a quasi generator, with order $2^{n-2}$ . Then each $5^{2m}$ generates a distinct residue, produced by some odd $x = 5^m$ . $\blacksquare$

Now for even $c$ , note that as $4 \mid x^2$ we must have $4 \mid c$ . Now do casework on $\frac{c}{4}$ . If we have $\frac{c}{4}$ is even then we reduce it by a factor of $4$ once more, else we can compute the number of odd residues modulo $2^{n-2}$ . In this way we can recurse to find, the number of odd QR's modulo $2^{n}$ is given by the sum of odd QRs congruent to $1$ modulo $8$ for $2^{n-2}$ , $2^{n-4}$ and so on.

Now to answer extract there are exactly $502 + 125 + 31 + 8 + 3 + 1 = \boxed{670}$ QRs in the given range.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

280 posts

#16 h Jan 6, 2024, 7:37 PM • 1 Y

Y by dolphinday

I claim that there are $670$ possible values of $c$ . Note that the problem is simply asking for all values $c$ such that $-c$ is a possible quadratic residue mod $2^{2007}$ . Using this, we will solve the problem as follows.

1. For every quadratic residue $p\equiv x^2 \mod 2^{2007}$ such that $p<2^{2007}$ , $\nu_2(p)$ is even.
In order to prove this, suppose that $\nu_2(x)=k$ and let $x=(2^k)q$ , where $q$ is odd. If we square $x$ , we get $(2^{2k})q^2$ . We now have a few cases.

If $2k<2007$ , then in order to get the quadratic residue value $p$ , we would have to subtract some nonnegative number of $2^{2007}$ 's. If $x^2$ is already less than $2^{2007}$ , then $\nu_2(p)=2k$ , proving our claim. If $x^2$ is greater than $2^{2007}$ , note that then $x^2-2^{2007}n$ for any positive integer $n$ would be $(2^{2k})(q^2-2^{2007-2k}n)$ , and since $2k<2007$ , this implies that $q^2-2^{2007-2k}n$ is odd. This gives that $\nu_2(p)=2k$ , proving our claim.

Finally, if $2k>2007$ , $p$ is simply $0$ , which is even. Therefore, if $p<2^{2007}$ is a quadratic residue of $2^{2007}$ , then $\nu_2(p)$ must be even.

2. Every odd quadratic residue $p<2^{2007}$ is $1$ mod $8$ .
Note that all squares are $1$ mod $8$ and $2^{2007}$ is a multiple of $8$ , proving our claim.

3. Every odd $p<2^{2007}$ such that $p\equiv 1 \mod 8$ is a quadratic residue mod $2^{2007}$ .
We can prove this by proving that by squaring the odd numbers from $1$ to $2^{2005}-1$ , inclusive, we get $2^{2004}$ different modulos mod $2^{2007}$ . We can prove this through contradiction.

Assume for the sake of contradiction, for distinct odd integers $x\neq y$ and $x,y<2^{2005}$ , $x^2\equiv y^2$ mod $2^{2007}$ . This would mean that
$x^2-y^2=(x-y)(x+y)\equiv 0 \mod 2^{2007}.$ Since $x$ and $y$ are both odd, one of $(x+y)$ and $(x-y)$ must be $2$ mod $4$ while the other is $0$ mod $4$ (this can be proved by taking cases mod $4$ ). However, note that since $x,y<2^{2005}$ , we have that $\max(\nu_2(x+y))+1=2006$ and $\max(\nu_2(x-y))+1=2005$ , meaning that $\max(\nu_2((x+y)(x-y)))=2006$ , which is less than $2007$ , a contradiction. Therefore every odd $p<2^{2007}$ such that $p\equiv 1 \mod 8$ is a quadratic residue mod $2^{2007}$ .

4. For some integer $p<2^{2007}$ such that $\nu_2(p)=2k$ and $p=2^{2k}q$ , $p$ is a quadratic residue mod $2^{2007}$ if and only if $q$ is $1$ mod $8$ .
Note that since $p<2^{2007}$ , we have that $2^{2k}<2^{2007}$ and therefore $2^{2k}\mid2^{2007}$ . Using this, we realize that if $x^2\equiv p \mod 2^{2007}$ , then we must have that $\nu_2(x)=k$ . Letting $x=2^ky$ for some odd integer $y$ , we get that
$2^{2k}q=p\equiv x^2\equiv2^{2k}y^2\mod2^{2007}\iff q\equiv y^2\mod2^{2007-2k}.$ We now take this in cases. Clearly, if $2k\leq 2004$ , the equation is equivalent to $q$ being equivalent to $y^2$ mod some multiple of $8$ . Since $y^2$ is odd, it must be $1$ mod $8$ , implying that $q$ is $1$ mod $8$ , proving our claim. Otherwise, if $2k=2006$ , we have that since $p<2^{2007}$ , $q$ must be $1$ mod $8$ , proving our claim. Therefore, for some integer $p<2^{2007}$ such that $\nu_2(p)=2k$ and $p=2^{2k}q$ , if $p$ is a quadratic residue mod $2^{2007}$ , then $q$ is $1$ mod $8$ .

Now for the other direction, note that since $q$ is $1$ mod $8$ , there exists an integer $y$ such that $y^2\equiv q\mod 2^{2007}$ by (3). Using this, note that
$(2^ky)^2\equiv (2^{2k})y^2\equiv 2^{2k}q \equiv p \mod 2^{2007},$ meaning that $p$ is a quadratic residue mod $2^{2007}$ , finishing our claim.

5. Finishing.
Combining the last four claims, we see that the only $c$ satisfies the problem conditions if and only if the power of $2$ factor of $-c$ mod $2^{2007}$ has an even exponent and the odd factor is $1$ mod $8$ . Using this and taking cases by $\nu_2(-c)$ , we get a total of $503+125+31+8+2+1$ , or $670$ possible values for $c$ , finishing the problem.

This post has been edited 2 times. Last edited by peppapig_, Mar 13, 2024, 3:40 PM
Reason: Purple C:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

241 posts

AlanLG

#17 h Jan 30, 2024, 11:57 PM

Y by

:coolspeak:

Claim. the odd quadractic residues $\pmod {2^k}$ are the $1\pmod 8$

Every odd square $\pmod {2^k}$ is $1\pmod 8$
This clearly true; note that there are $2^{k-3}$ numbers that are $1\pmod 8$ , so there are at most $2^{k-3}$ quadratic residues

Every $1\pmod 8$ is a odd square
We first gonna prove that $\operatorname{ord}_{2^k}(5)=2^{k-2}$ , this follows by LTE as
$k=\nu_2(5^{\operatorname{ord}{2^k}(5)}-1)=\nu_2(5-1)+\nu_2(5+1)+\nu_2(\operatorname{ord}{2^k}(5))-1$ The even power of $5$ covers all the numbers $1\pmod 8$ , then there are at least $\frac{\operatorname{ord}_{2^k}(5)}{2}=2^{k-3}$ $\text{distinct}$ quadratic residues.
So this two sets are the same, as desired.

Now, we want to count all quadratic residues, which are equivalent to all $x$ with $\nu_2(x)$ even and with odd part being $1\pmod 8$ some computation gives the answer is $670$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2534 posts

#18 h Feb 12, 2024, 8:14 PM

Y by

Rephrase the problem as follows. Find the quadratic residues of $2^{2007}$ .

We will find a general form for $2^n$ : realize that we only need to compute odd quadratic residues, as we can tack on $2^{2k}$ onto any given odd quadratic residue to create an even one.

Claim 1: All odd quadratic residues $c$ must satsify $c \equiv 1 \pmod{8}$ .

Proof: Let $x=2k+1$ . We have

$x^2 = (2k+1)^2 = 4k(k+1)+1 \equiv c \equiv 1 \pmod{8},$
as desired. $\square$

Claim 2: All numbers $c \equiv 1 \pmod{8}$ are odd quadratic residues.

Proof: We will use $5$ as a generator. Let $o$ be the order of $5$ modulo $2^n$ . Then,

$5^o - 1 \equiv 0 \pmod{2^n} \iff \nu_2(5^o-1) \ge n.$
Lifting the Exponent gives

$\nu_2(5^o-1) = \nu_2(5-1) + \nu_2(o) \ge n \implies o = 2^{n-2}.$
This means that every $5^{2a}$ generates a unique quadratic residue, and there are at least $2^{n-3}$ of them. $\square$

Remark: LTE applies here for $p=2$ since the condition $4 \mid x-y$ is satisfied.

At this point, casework on the number of appended powers of $2$ yields $\boxed{670}$ as our answer.

This post has been edited 1 time. Last edited by joshualiu315, Feb 12, 2024, 8:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

796 posts

#19 h Feb 28, 2024, 5:10 AM

Y by

We first note that an odd integer is a quadratic residue modulo $2^n$ (where $n \ge 3$ ) iff it is $1 \pmod 8$ . This follows by induction - if there exists a value of $x=k$ with $x^2 \equiv m \pmod{2^n}$ , we use $x=k+2^n$ and $x=k+2^{n-1}$ to generate the residues $m$ and $m+2^n$ . Also notice that a residue modulo $2^{n+1}$ must be a residue modulo $2^n$ , so we cannot gain new residues.

Now we investigate the case when $c$ is even. If $v_2(c)$ is odd, then $v_2(x^2+c)$ is bounded as we won't have $v_2(x^2) = v_2(c)$ . Otherwise, we let $x=2^{v_2(c)/2} \cdot y$ to get
$2^{2007} \mid x^2+c = 2^{v_2(c)}(y^2 + o),$
where $o$ now must be odd, so $o \equiv 7 \pmod 8$ . In conclusion, $c$ must be of the form $(8i+7) \cdot 2^{2j}$ or 0, giving us $\boxed{670}$ possibilities. $\blacksquare$

This post has been edited 1 time. Last edited by shendrew7, Mar 1, 2024, 4:20 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5608 posts

#20 h Jan 4, 2025, 1:41 PM • 1 Y

Y by MS_asdfgzxcvb

Solved a while ago but forgot to post

Claim: For any positive integer $n\ge 3$ , a positive integer $r<2^n$ is a quadratic residue $\pmod{2^n}$ , iff $r\equiv 1\pmod 8$ .
Proof: Clearly if $r\not\equiv 1\pmod 8$ , then any positive integer $r\pmod{2^n}$ is not $1\pmod 8$ and thus cant be perfect square. So $r\equiv 1\pmod 8$ .

Now we show that there are exactly $2^{n-3}$ odd quadratic residues $\pmod{2^n}$ . Clearly there must be at most $\frac{2^n }{8} = 2^{n-3}$ of them.

Suppose odd $1\le a,b< 2^{n-2}$ satisfy $a^2 \equiv b^2 \pmod{2^n}$ , and $a\ne b$ .

Then we have $n\le \nu_2(a^2 - b^2) = \nu_2(a-b) + \nu_2(a+b)$ Now, $a-b$ and $a+b$ have a difference of $2b$ , so exactly one of them is not a multiple of $4$ . Thus either $2^{n-1}\mid a-b$ or $2^{n-1}\mid a+b$ , both of which are absurd.

There are exactly $2^{n-3}$ odd numbers between $1$ and $2^{n-2}$ , so we have exactly $2^{n-3}$ odd QRs $\pmod{2^n}$ . This proves that everything $1\pmod 8$ is a QR $\pmod{2^n}$ . $\square$

Thus, if $m = 2^k \cdot t$ , where $t$ is odd, then $m$ is a QR iff $k$ is even and $t\equiv 1\pmod 8$ .

Now we answer extract, where $n=2007$ . The problem condition is equivalent to $x=-c$ being a QR $\pmod{2^{2007}}$ , where $-2007\le x\le 2007$ .

Let $f(x) = \frac{x}{\nu_2(x)}$ .

If $\nu_2(x) = 0$ , then we have $f(x)\in \{-2007, -1999, \ldots, 2001\}$ , which is in total $502$ numbers.

If $\nu_2(x) = 2$ , then we have $f(x)\in \{-495, -487, \ldots, 497\}$ , which is in total $125$ numbers.

If $\nu_2(x) = 4$ , then we have $f(x)\in \{-119, -111, \ldots, 121\}$ , which is in total $31$ numbers.

If $\nu_2(x) = 6$ , then we have $f(x)\in \{-31, -23, \ldots, 25\}$ , which is in total $8$ numbers.

If $\nu_2(x) = 8$ , then we have $f(x)\in \{-7,1\}$ , which is in total $2$ numbers.

If $\nu_2(x) = 10$ , then we have $f(x) = 1$ .

Clearly if $x\ne 0$ , $\nu_2(x) > 10$ is not possible.

If $x=0$ , then we have $1$ value of $x$ .

Counting up, the answer is $502 + 125 + 31 + 8 + 2 + 1 + 1 = \boxed{670}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

235 posts

#21 h Apr 9, 2025, 9:14 AM

Y by

Main Claim: For $n \ge 3$ , we have $a$ is an odd QR $\bmod$ ${2^n}$ iff $a \equiv 1 \pmod 8$ .
Proof: One direction is obvious as $1$ i only odd QR $\bmod 8$ . For the other direction see that if $x$ , $y$ odd then $x^2 \equiv y^2 \pmod {2^n} \iff x \equiv \pm y \pmod {2^{n-1}}$ See that this gives us that there exactly $2^{n-3}$ odd QRs, which means all $1 \pmod 8$ numbers are QRs. $\square$

Let $2^rb$ is a QR where $b$ is odd, then it is equivalent that $b \equiv 1 \pmod 8$ and $r$ is even.

Now do a little computation and see that answer is $\boxed{670}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

634 posts

cursed_tangent1434

#22 h Apr 10, 2025, 6:00 AM

Y by

We claim that the answer is $\boxed{670}$ which is the number of integers of the form $2^{2r}\cdot a$ for some non-negative integer $r$ and $a \equiv 7 \pmod{8}$ (or $a=0$ ). We shall first show that all $c$ for which such an integer $x$ exists must be of the prescribed form.

If $c=0$ it is clear that $x=2^{1004}$ satisfies the desired constraints so in what follows we consider $c \ne 0$ . Further, if $\nu_2(c)$ is odd it is clear that $\nu_2(x^2) \ne \nu_2(c)$ so
$\nu_2(x^2+c) = \min(2\nu_2(x),\nu_2(c)) \le \nu_2(c) < 2007$ since $|c| \le 2007 < 2^{2007}$ . This is a clear contradiction which implies that $\nu_2(c)$ is even. Thus, $c$ must be of the form $2^{2r}a$ for some odd integer $a$ .

Now, as noted before if $\nu_2(x^2) \ne \nu_2(c)$ we have a contradiction so this implies that $\nu_2(x)=r$ . So we can write $x^2=2^{2r}y^2$ for some odd integer $y$ . Plugging this expressions into the desired divisibility we have,
$2^{2007} \mid x^2+c=2^{2r}(y^2+a)$ so we have that $2^{1997}\mid2^{2007-2r} \mid y^2+a$ as $r \le 10$ since $|c| \le 2007$ .

Now, note that $a \not \equiv 1 \pmod{4}$ since then $y^2+t \in \{2,3\} \pmod{4}$ which implies that the right-hand side is not even divisible by 4. Thus, we must have $a \equiv 3 \pmod{4}$ and we can write $a=4k+s$ for some integer $k$ . Further, we can write $y=2z+1$ for some integer $z$ . Plugging this relations into the given divisibility we have,
$2^{1997} \mid y^2+a=(2z+1)^2+(4k+3) = 4(z(z+1)+k+1)$ which implies that $k$ must be odd. Thus, $a=4k+3=4(2l+1)+3=8l+7$ which implies that $a \equiv 7 \pmod{8}$ as desired.

We now show that all integers $c$ of the aforementioned forms indeed do satisfy the given condition. We do this via induction, showing that there exists a positive integer $x_i$ such that $2^{i+2}\mid x_i^2 + c$ for each odd $c \equiv 7 \pmod{8}$ for all $i\ge 1$ which solves the problem.

The base case is immediate since $x_1=1$ makes $x_1^2+c = c+1 \equiv 0 \pmod{8}$ . Now, say there exists some positive integer $x_i$ such that $2^{i+2}\mid x_i^2 + c$ for some $i \ge 1$ . Now, if $2^{i+3}\mid x_i^2 + c$ we let $x_{i+1}=x_i$ . Else, let $x_{i+1}=x_i+2^{i}$ . Note,
$x_{i+1}^2 +c = (x_i+2^{i+1})^2 +c = (x_i^2+c) + 2^{i+2}+2^{2i+2} \equiv (x_i^2+c) + 2^{i+2} \pmod{2^{i+3}}$ since $2i+2 \ge i+3$ for all $i \ge 1$ . Now, since $2^{i+2}\mid x_i^2 + c$ but $2^{i+3}\nmid x_i^2 + c$ we have that $x_i^2 + c \equiv 2^{i+2} \pmod{2^{i+3}}$ which implies that $2^{i+3}\mid x_{i+1}^2 + c$ as desired. This completes the induction, and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

651 posts

#23 h Apr 26, 2025, 12:00 AM

Y by

We are computing when $-c$ is a quadratic residue modulo $2^{2007}.$ We will look at modulo $2^n.$ I claim that the odd quadratic residues modulo are values $k\equiv1\pmod8.$

We prove this with induction. For the first 3 powers, this is trivially true. Assume that if $n\leq k,$ these are the only odd quadratic residues. Assume $k\geq2$

For $n = k + 1,$ we have that any value that is $3, 5, 7\pmod8$ aren't a perfect square. Let $a \equiv 1\pmod 8.$ Let $a\equiv l^2\pmod{2^k}.$ We have that:
\begin{itemize}
\item $(l + 2^{k})^2 \equiv l^2 + l2^{k + 1} + 2^{2k}\equiv l^2\pmod{2^{k + 1}}$
\item $(l + 2^{k - 1})^2 \equiv l^2 + 2^kl + 2^{2k - 2}.$ However, since $2k - 2 \geq k + 1,$ $(l + 2^{k - 1})^2 \equiv l^2 + 2^k \equiv a\pmod{2^{k + 1}}$
\end{itemize}
Thus, $2^{2k}q$ are all quadratic residues, where $k\in\mathbb N, q\equiv1\pmod8.$ If $k = 0,$ the solves are $\{-2007, \ldots, 2001\},$ with $502$ solutions. If $k = 1,$ the solves are $125.$ By continuing, the answer is $502 + 125 + 31 + 8 + 2 + 1 + 1 = \boxed{670}$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a