# 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 $\displaystyle p>3, \; (3,p)=1 \implies 3^{-1}$ exists. Let $\displaystyle a_p\equiv3^{-1} \bmod{p}$.

Set $\displaystyle 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:

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

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

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

Pretty messy huh?

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

Set $\displaystyle 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 $\displaystyle 3n^2-5n+1=0\!\!\!\pmod p\Longrightarrow n^2-5a_pn+a_p=0\!\!\!\pmod p$ $\displaystyle \Longrightarrow n^2-5a_pn=-a_p\!\!\!\pmod p$

Complete the square:

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

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

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

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

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

Pretty nice piece of work, indeed!

Tonio

where $\displaystyle \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 $\displaystyle p=13\Longrightarrow$ it must be that $\displaystyle -3^{-1}+25\cdot 4^{-1}\cdot 9^{-1}$ is a square modulo 13, but:

$\displaystyle -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. $\displaystyle (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 $\displaystyle 3\cdot 9-5\cdot 3+1=13=0\!\!\!\pmod{13}$

And with $\displaystyle 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!