# Thread: Determine which primes > 3 divide...

1. ## Determine which primes > 3 divide...

Determine which primes > 3 divide some number of the form 3n^2 - 5n + 1 and which do not.

2. Since $p>3, \; (3,p)=1 \implies 3^{-1}$ exists. Let $a_p\equiv3^{-1} \bmod{p}$.

Set $3n^2+5n-1\equiv0\bmod{p}\implies n^2+5a_pn-a_p\equiv0\bmod{p}\implies n^2+5a_pn\equiv a_p\bmod{p}$.

Complete the square:

$(n+5\cdot2^{-1}\cdot a_p)^2\equiv 3^{-1}+25\cdot 4^{-1}\cdot a_p^2 \bmod{p}$

(again $2^{-1}$ and $4^{-1}$ exist since $p>2$).

So a solution exists (i.e. $p$ divides this polynomial for some $n$) $\iff \left(\frac{3^{-1}+25\cdot 4^{-1}\cdot 9^{-1}}{p}\right) = 1$, where $\left(\frac xp\right)$ is the Legendre symbol.

Pretty messy huh?

3. Originally Posted by chiph588@
Since $p>3, \; (3,p)=1 \implies 3^{-1}$ exists. Let $a_p\equiv3^{-1} \bmod{p}$.

Set $3n^2+5n-1\equiv0\bmod{p}\implies n^2+5a_pn-a_p\equiv0\bmod{p}\implies n^2+5a_pn\equiv a_p\bmod{p}$.

Typo: it must be $3n^2-5n+1=0\!\!\!\pmod p\Longrightarrow n^2-5a_pn+a_p=0\!\!\!\pmod p$ $\Longrightarrow n^2-5a_pn=-a_p\!\!\!\pmod p$

Complete the square:

$(n+5\cdot2^{-1}\cdot a_p)^2\equiv 3^{-1}+25\cdot 4^{-1}\cdot a_p^2 \bmod{p}$

It must be: $(n-5\cdot 2^{-1}a_p)^2=(-3^{-1}+25\cdot 4^{-1}\cdot 9^{-1})\!\!\!\pmod p$

(again $2^{-1}$ and $4^{-1}$ exist since $p>2$).

So a solution exists (i.e. $p$ divides this polynomial for some $n$) $\iff \left(\frac{3^{-1}+25\cdot 4^{-1}\cdot 9^{-1}}{p}\right) = 1$,

[color=red]"...if $\left(\frac{-3^{-1}+25\cdot 4^{-1}\cdot 9^{-1}}{p}\right) = 1$"

Pretty nice piece of work, indeed!

Tonio

where $\left(\frac xp\right)$ is the Legendre symbol.

Pretty messy huh?
.

4. Originally Posted by tonio
.

Not only the above tells you what primes divide the quadratic in n but it also tells you how to find the n's!

For example, take $p=13\Longrightarrow$ it must be that $-3^{-1}+25\cdot 4^{-1}\cdot 9^{-1}$ is a square modulo 13, but:

$-3^{-1}+25\cdot 4^{-1}\cdot 9^{-1}=-9-1\cdot 10\cdot 3=-9-30=-39=0\!\!\!\pmod{13}\Longrightarrow$ we've a solution for each n s.t. $(n-5\cdot 2^{-1}\cdot3^{-1})^2=(n-5\cdot 7\cdot 9)^2=(n-3)^2= 0\!\!\!\pmod{13}\iff n=3\!\!\!\pmod{13}$ , and choosing n=3 we indeed get $3\cdot 9-5\cdot 3+1=13=0\!\!\!\pmod{13}$

And with $16=3\!\!\!\pmod{13}\,,\,\,3\cdot 16^2-5\cdot 16+1=689=13\cdot 53=0\!\!\!\pmod {13}$ and etc.

Very beautiful

Tonio

5. Whoops! Typo's!