Quadratic residues and partitioning

**Bacterius** · March 28th 2010, 08:03 PM

Hello,
given $n$ any composite number, and $x^2 \equiv y \pmod{n}$ , $x \neq y$ , am I guaranteed of finding a "partitioning" of $y$ such that $x^2 - y = x^2 + bx + c$ for any $b, c \in \mathbb{Z}$ satisfying the condition $b^2 - 4c$ a perfect square? And if yes, are there some predisposed values of $x$ for which it works? And (sorry) if the previous question has a negative answer, is there an easy way of finding the values of $b$ and $c$ that produce a perfect square given $x$ and $y$ ?

For instance, if $n = 77$ , we choose say $x = 19$ , and therefore $y = 53$ , so we get $19^2 - 53$ . This can be written as $19^2 - 19 \times 2 - 15$ , and $2^2 - 4 \times (-15) = 64$ which is a perfect square.

Additional information :
- the prime factorization of $n$ will not be used.

(for the curious, this leads to a factorization of $n$ - the perfect square requirement is necessary otherwise one needs to take square roots modulo $n$ )

Thank you

**chiph588@** · March 28th 2010, 08:11 PM

Originally Posted by Bacterius

Hello,
given $n$ any composite number, and $x^2 \equiv y \pmod{n}$ , $x \neq y$ , am I guaranteed of finding a "partitioning" of $y$ such that $x^2 - y = x^2 + bx + c$ for any $b, c \in \mathbb{N}$ satisfying the condition $b^2 - 4c$ a perfect square? And if yes, are there some predisposed values of $x$ for which it works? And (sorry) if the previous question has a negative answer, is there an easy way of finding the values of $b$ and $c$ that produce a perfect square given $x$ and $y$ ?

For instance, if $n = 77$ , we choose say $x = 19$ , and therefore $y = 53$ , so we get $19^2 - 53$ . This can be written as $19^2 - 19 \times 2 - 15$ , and $2^2 - 4 \times (-15) = 64$ which is a perfect square.

Additional information :
- the prime factorization of $n$ will not be used.

(for the curious, this leads to a factorization of $n$ - the perfect square requirement is necessary otherwise one needs to take square roots modulo $n$ )

Thank you

Not quite sure if I understand what your asking, but if we let $x=3$ , $y=4$ , and $n=5$ we get $x^2\equiv y\mod{n}$ .

Now we want $b,c\in\mathbb{N}$ such that $-y=3b+c$ . This is impossible however, since the left hand side is negative and the right hand side is positive...

**Bacterius** · March 28th 2010, 08:19 PM

You are right, (but $5$ is a prime number). Sorry (I always make that mistake for some reason! $b, c \in \mathbb{Z}$ ). I'll correct.

**chiph588@** · March 28th 2010, 08:47 PM

Your conditions boil down to a system of equations.
$\begin{cases} xb+c=-y\\b^2-4c=k^2 \end{cases}$
This last equation is asking if $b^2-4c$ is ever a square.

From this we can get $b=-2x\pm\sqrt{4x^2+k^2-y}$

Thus we require $4x^2+k^2-y$ to be square since we're wanting $b\in\mathbb{Z}$ .

So let's try an example:
Let $n=10$ , $x=4 \implies y=6$ .
We then get $b=-8\pm\sqrt{58+k^2}$ , so now we need to see if $k^2+58$ is ever square.

We now must solve $k^2-m^2+58=0$ ,or $(k+m)(k-m)=-58$

You could then find the prime factorization of $58$ and test the finite amount of cases to solve for $k$ and $m$ ...
Or you could just believe me when I say there are no solutions in $\mathbb{Z}$ .

This means there is no $k\in\mathbb{Z}$ such that $b^2-4c=k^2$ for this particular example.

Thus we aren't always guaranteed there to be a square $b^2-4c$ that satisfies your conditions.

**Bacterius** · March 28th 2010, 08:59 PM

Thanks!

**pollardrho06** · March 29th 2010, 06:13 AM

Good stuff!

Thread: Quadratic residues and partitioning

LinkBack

Thread Tools

Display

Quadratic residues and partitioning

Similar Math Help Forum Discussions

Sum of quadratic residues

Quadratic Residues

Quadratic residues

Quadratic Residues

Quadratic Residues

Search Tags