C 1

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

w

0 users

TOPICS

No tags match your search

M

No tags match your search

M

C 1

G H J

Reveal topic tags

Quadratic Residues

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

3615 posts

Peter

#1 h May 25, 2007, 12:24 AM • 2 Y

Y by Adventure10 and 1 other user

Find all positive integers $n$ that are quadratic residues modulo all primes greater than $n$ .

Z K Y

The post below has been deleted. Click to close.

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

1198 posts

Megus

#2 h May 25, 2007, 12:24 AM • 2 Y

Y by Adventure10 and 1 other user

Let $n=2^k\prod _1 ^m q_i \cdot a^2$

There exists infinitely many primes $p$ for which $2^k\prod _1 ^m q_i$ is non-residue mod $p$ (by Chinese remainder theorem and Dirichlet's theorem), hence $n$ has to be a square and obviously all such numbers satisfy conditions of the problem.

Z K Y

The post below has been deleted. Click to close.

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

7579 posts

ZetaX

#3 h May 25, 2007, 12:24 AM • 2 Y

Y by Adventure10 and 1 other user

We can avoid Dirichlet (the only analytical step) by using quadratic reciprocity for Jacobi symbols (the rest of the proof being the same).

Here an adapted copy of more or less the same from a post of mine on MathLinks:

Assume that $n$ isn't a square, but a square $\mod$ all primes $>n$ .

Let $n=2^s b = 2^s p_1^{v_1} p_2^{v_k} ... p_k^{v_k}$ be the prime factorisation and $b$ it's greatest odd factor. Since $n$ is not a square, either (w.l.o.g.) $v_1$ is odd or $s$ is odd.

1. case: all $v_i$ are even, so $s$ is odd.
Then simply taking an integer $q$ (coprime to all primes $\leq n$ ) not dividing $n$ and $\equiv 3\mod 8$ gives $\left( \frac{n}{q} \right) = \left( \frac{2^s}{q} \right) \left( \frac{b}{q} \right) = (-1)^s = -1$ .

2. case: $v_1$ is odd.
Now let $c$ be a quadratic non-residue $\mod p_1$ and take an integer $q$ (coprime to all primes $\leq n$ ) such that $q \equiv 1 \mod 8$ , $q \equiv c \mod p_1$ and $q \equiv 1 \mod p_i$ for all other $p_i$ .
Then we get:
$\left( \frac{n}{q} \right) = \left( \frac{2}{q} \right)^s \left( \frac{p_1}{q} \right)^{v_1} \left( \frac{p_2}{q} \right)^{v_2} ... \left( \frac{p_k}{q} \right)^{v_n} = \left( \frac{q}{p_1} \right)^{v_1} \left( \frac{q}{p_2} \right)^{v_2} ... \left( \frac{q}{p_k} \right)^{v_k}=(-1)^{v_1}=-1$ .

In both cases, $n$ is not a quadratic residue $\mod q$ , thus not for at least one of it's prime divisors. This contradicts the assumption of $n$ being a square $\mod$ all primes $>n$ .

There are some tough ones:

1. If $n$ is a $k$ -th power $\mod$ all primes $p>n$ , then:
- $8 \nmid k$ ; then $n$ is a $k$ -th power of an integer.
- $8 | k$ ; then $n$ is a $\frac{k}{2}$ -th power of an integer.

2. If $n$ is a power of $2$ $\mod$ all primes $p>n$ , then $n$ is also a power of $2$ seen as an integer.

Z K Y

The post below has been deleted. Click to close.

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

1 post

#4 h Jun 25, 2013, 1:29 AM • 2 Y

Y by Adventure10, Mango247

ZetaX wrote:

We can avoid Dirichlet (the only analytical step) by using quadratic reciprocity for Jacobi symbols (the rest of the proof being the same).

Here an adapted copy of more or less the same from a post of mine on MathLinks:

Assume that $n$ isn't a square, but a square $\mod$ all primes $>n$ .

Let $n=2^s b = 2^s p_1^{v_1} p_2^{v_k} ... p_k^{v_k}$ be the prime factorisation and $b$ it's greatest odd factor. Since $n$ is not a square, either (w.l.o.g.) $v_1$ is odd or $s$ is odd.

1. case: all $v_i$ are even, so $s$ is odd.
Then simply taking an integer $q$ (coprime to all primes $\leq n$ ) not dividing $n$ and $\equiv 3\mod 8$ gives $\left( \frac{n}{q} \right) = \left( \frac{2^s}{q} \right) \left( \frac{b}{q} \right) = (-1)^s = -1$ .

2. case: $v_1$ is odd.
Now let $c$ be a quadratic non-residue $\mod p_1$ and take an integer $q$ (coprime to all primes $\leq n$ ) such that $q \equiv 1 \mod 8$ , $q \equiv c \mod p_1$ and $q \equiv 1 \mod p_i$ for all other $p_i$ .
Then we get:
$\left( \frac{n}{q} \right) = \left( \frac{2}{q} \right)^s \left( \frac{p_1}{q} \right)^{v_1} \left( \frac{p_2}{q} \right)^{v_2} ... \left( \frac{p_k}{q} \right)^{v_n} = \left( \frac{q}{p_1} \right)^{v_1} \left( \frac{q}{p_2} \right)^{v_2} ... \left( \frac{q}{p_k} \right)^{v_k}=(-1)^{v_1}=-1$ .

In both cases, $n$ is not a quadratic residue $\mod q$ , thus not for at least one of it's prime divisors. This contradicts the assumption of $n$ being a square $\mod$ all primes $>n$ .

There are some tough ones:

1. If $n$ is a $k$ -th power $\mod$ all primes $p>n$ , then:
- $8 \nmid k$ ; then $n$ is a $k$ -th power of an integer.
- $8 | k$ ; then $n$ is a $\frac{k}{2}$ -th power of an integer.

2. If $n$ is a power of $2$ $\mod$ all primes $p>n$ , then $n$ is also a power of $2$ seen as an integer.

Thank you thank you thank you!

You wouldn't believe how long i have been trying to find the answer to this!

Thank you so much ZetaX,

Laura

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a