LinkBack URL
About LinkBacksDetermine which primes > 3 divide some number of the form 3n^2 - 5n + 1 and which do not.
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?
.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?
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
  |
