Find the primes,for which a relation is satisfied

[evinda]

Hey! (Wave)

I have to find the primes $p$,for which $x^2 \equiv 13 \pmod p$ has a solution.

That's what I have tried:

$$\text{ Let } p>13:$$
We want that $\displaystyle{ \left ( \frac{13}{p} \right )}=1$

$$\left ( \frac{13}{p} \right )=(-1)^{\frac{13-1}{2} \cdot \frac{p-1}{2}}\left ( \frac{p}{13} \right ) $$

As $(-1)^{\frac{13-1}{2}=1, \text{ it must be: } \frac{p-1}{2}}\left ( \frac{p}{13} \right )=1$

So, $x^2 \equiv p \pmod{13}$ should have a solution..

Is that what I have tried right? Also,what else could I do? (Thinking)

 

[I like Serena]

Hi! (Happy)

Hey! (Wave)

I have to find the primes $p$,for which $x^2 \equiv 13 \pmod p$ has a solution.
So, $x^2 \equiv p \pmod{13}$ should have a solution..

Is that what I have tried right? Also,what else could I do? (Thinking)

Looks good! (Nod)

What you can do is continue.
Which squares are there? (Thinking)

The first square is with $x=1$ in which case we get $p \equiv 1^2 \pmod{13}$.
So the original equation would have a solution if $p$ is an odd prime of the form $1+13k$.
And since $p$ has to be odd, we can also write it as $1+26k$.
First option that is prime is $53$.
And indeed, with e.g. $x=15$ we find $x^2 \equiv 15^2 \equiv 13 \pmod{53}$. (Mmm)

Btw, there's no need to require $p > 13$. You only need that it is odd.
So don't forget $p=2$. Is there a solution in that case? (Wondering)

 

[evinda]

Hi! (Happy)
Looks good! (Nod)

What you can do is continue.
Which squares are there? (Thinking)

The first square is with $x=1$ in which case we get $p \equiv 1^2 \pmod{13}$.
So the original equation would have a solution if $p$ is an odd prime of the form $1+13k$.
And since $p$ has to be odd, we can also write it as $1+26k$.
First option that is prime is $53$.
And indeed, with e.g. $x=15$ we find $x^2 \equiv 15^2 \equiv 13 \pmod{53}$. (Mmm)

Btw, there's no need to require $p > 13$. You only need that it is odd.
So don't forget $p=2$. Is there a solution in that case? (Wondering)

I created this array:

$$\begin{bmatrix}
x \ \ |& 1 & 2 &3 &4 &5 &6 \\
\ \ \ \ |& - & - & - & - & - & -\\
x^2 \ | & 1 & 4 & 9 & 3 & 12 & 10
\end{bmatrix}$$

So, is it only possible that $p \equiv 3 \pmod{13}$,because the only prime at the square residues is $3$ ,or am I wrong? (Sweating)

 

[I like Serena]

I created this array:

$$\begin{bmatrix}
x \ \ |& 1 & 2 &3 &4 &5 &6 \\
\ \ \ \ |& - & - & - & - & - & -\\
x^2 \ | & 1 & 4 & 9 & 3 & 12 & 10
\end{bmatrix}$$

So, is it only possible that $p \equiv 3 \pmod{13}$,because the only prime at the square residues is $3$ ,or am I wrong? (Sweating)

Remember that $p \equiv 3 \pmod{13}$ means that $p=3+13k$. So this is not only $p=3$, but also $p=16, 29, ...$. As you can see $p=29$ is also a prime. (Wasntme)

Each of the residues will generate primes.

What about $x\equiv 0$? (Wondering)

 

[evinda]

Remember that $p \equiv 3 \pmod{13}$ means that $p=3+13k$. So this is not only $p=3$, but also $p=16, 29, ...$. As you can see $p=29$ is also a prime. (Wasntme)

Each of the residues will generate primes.

What about $x\equiv 0$? (Wondering)

Shouldn't it be $(x,13)=1$ ? (Thinking)

So can I just say that the relation is satisfied only for primes of the form $13k+3$? Or not? (Sweating)

 

[I like Serena]

Shouldn't it be $(x,13)=1$ ? (Thinking)

I see no reason why it should.
Let's see what happens with $p=13$ in the original equation.
Does $x^2 \equiv 13 \pmod {13}$ have a solution? (Wondering)

So can I just say that the relation is satisfied only for primes of the form $13k+3$? Or not? (Sweating)

There are many more.
Pick $x\equiv 1$ and we find $p \equiv 1 \pmod{13}$.
Now $1$ may not be a prime, but $1+4\cdot 13 = 53$ is a prime... (Thinking)

 

[evinda]

I see no reason why it should.

I thought it,because,according to my notes, if $x$ is a solution of $x^2 \equiv a \pmod m$,then $(x,m)=1$..So isn't it also like that in our case?

Let's see what happens with $p=13$ in the original equation.
Does $x^2 \equiv 13 \pmod {13}$ have a solution? (Wondering)

No,it has no solution,because $(13,13)=13 \neq 1$..or am I wrong?

There are many more.
Pick $x\equiv 1$ and we find $p \equiv 1 \pmod{13}$.
Now $1$ may not be a prime, but $1+4\cdot 13 = 53$ is a prime... (Thinking)

$$\begin{bmatrix}
x \ \ |& 1 & 2 &3 &4 &5 &6 \\
\ \ \ \ |& - & - & - & - & - & -\\
x^2 \ | & 1 & 4 & 9 & 3 & 12 & 10
\end{bmatrix}$$

So..do we maybe see from the array that all the possible primes are of the form $13k+1, 13k+4, 13k+9 ,13k+3,13k+12 \text{ or } 13k+10$ ?? Or can't we do it like that? (Sweating)

 

[I like Serena]

I thought it,because,according to my notes, if $x$ is a solution of $x^2 \equiv a \pmod m$,then $(x,m)=1$..So isn't it also like that in our case?

If you look at the definition of the Legendre symbol, you'll see that $x\equiv a \equiv 0$ is allowed.
It does mean that $\left(\frac a p\right)$ has the special value of $0$.

Anyway, there's no need to put in that restriction.
As I see it, it should not be there unless specifically mentioned in the problem statement (which would not be unusual). (Wasntme)

No,it has no solution,because $(13,13)=13 \neq 1$..or am I wrong?

If we drop that restriction, it does have a valid and sensible solution. (Wasntme)

$$\begin{bmatrix}
x \ \ |& 1 & 2 &3 &4 &5 &6 \\
\ \ \ \ |& - & - & - & - & - & -\\
x^2 \ | & 1 & 4 & 9 & 3 & 12 & 10
\end{bmatrix}$$

So..do we maybe see from the array that all the possible primes are of the form $13k+1, 13k+4, 13k+9 ,13k+3,13k+12 \text{ or } 13k+10$ ?? Or can't we do it like that? (Sweating)

Yep. We can do it like that.
I'd say: odd primes of the form $13k\pm 1, 13k\pm 3, 13k\pm 4$, which is shorter.
Or: primes of the form $26k\pm 1, 26k\pm 3, 26k + 13 \pm 4$.
... and we might also mention the solution when $x\equiv 0$.
... and we might check the case $p=2$ separately, since we were only looking at odd primes. (Wink)

 

[evinda]

If you look at the definition of the Legendre symbol, you'll see that $x\equiv a \equiv 0$ is allowed.
It does mean that $\left(\frac a p\right)$ has the special value of $0$.

Anyway, there's no need to put in that restriction.
As I see it, it should not be there unless specifically mentioned in the problem statement (which would not be unusual). (Wasntme)
If we drop that restriction, it does have a valid and sensible solution. (Wasntme)

Yep. We can do it like that.
I'd say: odd primes of the form $13k\pm 1, 13k\pm 3, 13k\pm 4$, which is shorter.
Or: primes of the form $26k\pm 1, 26k\pm 3, 26k + 13 \pm 4$.
... and we might also mention the solution when $x\equiv 0$.
... and we might check the case $p=2$ separately, since we were only looking at odd primes. (Wink)

I understand (Sun) Thanks a lot! (Mmm)