Determine which primes > 3 divide...

**NikoBellic** · Apr 12th 2010, 05:23 PM

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

**chiph588@** · Apr 12th 2010, 08:18 PM

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?

**tonio** · Apr 13th 2010, 03:07 AM

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?

.

**tonio** · Apr 13th 2010, 03:18 AM

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

**chiph588@** · Apr 13th 2010, 03:38 PM

Whoops! Typo's!

Thread: Determine which primes > 3 divide...

LinkBack

Thread Tools

Display

Determine which primes > 3 divide...

Similar Math Help Forum Discussions

[SOLVED] gcd(a,b) = 1 iff no primes divide a and b

[SOLVED] How to divide GCF through...

Divide

Determine whether these sets S are bounded, and determine sup(S) and inf(S) if they e

Let P be the set of primes that divide 200!.

Search Tags