Find all primes p such that [math]\frac{10}{p}[/math]=1.

**mancillaj3** · April 14th 2009, 12:08 PM

Find all primes p such that $(\frac{10}{p})=1$

**PaulRS** · April 14th 2009, 01:49 PM

First: $ \left( {\tfrac{{10}} {p}} \right)_L = \left( {\tfrac{2} {p}} \right)_L \cdot \left( {\tfrac{5} {p}} \right)_L $

You should know that: $ \left( {\tfrac{2} {p}} \right)_L = \left( { - 1} \right)^{\tfrac{{p^2 - 1}} {8}} $ ( If you don't, this can be deduced easily from Gauss' Lemma )

By the Quadratic Reciprocity Theorem: $ \left( {\tfrac{5} {p}} \right)_L \cdot \left( {\tfrac{p} {5}} \right)_L = \left( { - 1} \right)^{\tfrac{{5 - 1}} {2} \cdot \tfrac{{p - 1}} {2}} = \left( { - 1} \right)^{p - 1} = 1 $ hence $ \left( {\tfrac{5} {p}} \right)_L = \left( {\tfrac{p} {5}} \right)_L $

And by Euler's Criterion: $ \left( {\tfrac{p} {5}} \right)_L \equiv p^2 \left( {\bmod .5} \right) $

So what we actually want is: $ p^2 \cdot \left( { - 1} \right)^{\tfrac{{p^2 - 1}} {8}} \equiv 1\left( {\bmod .5} \right) $

Let's go over all the possible remainders module 5:

Case: $ p = 5k + 1 $ here we must have: $ \left( { - 1} \right)^{\tfrac{{5^2 k^2 + 10k}} {8}} = 1 $ $ \Rightarrow 16\left| {\left( {5k^2 + 2k} \right)} \right. $ so k is even: $ k = 2k_1 \Rightarrow 5^2 k^2 + 10k = 4 \cdot \left( {5 \cdot k_1 ^2 + k_1 } \right) $ $ \Rightarrow 4\left| {\left[ {k_1 \cdot \left( {5 \cdot k_1 + 1} \right)} \right]} \right. $ and this can happen if and only if $ {4\left| {k_1 } \right.} $ or $ {k_1 = 4k_2 +3} $ and so we have either: $ \left. 8 \right|k $ or $ k = 8k_2 + 6 $ this means that we must have: $ p \equiv 1\left( {\bmod .40} \right) \vee p \equiv 31\left( {\bmod .40} \right) $
Case: $ p = 5k - 1 $ ( the 'similar' case, just change the sign - check it-), we get: $ p \equiv -1\left( {\bmod .40} \right) \vee p \equiv -31\left( {\bmod .40} \right) $
Case: $p=5k-3$ : here we require $ \left( { - 1} \right)^{\tfrac{{p^2 - 1}} {8}} = \left( { - 1} \right)^{\tfrac{{5^2 k^2 - 30k + 8}} {8}} = - 1 $ so we must have: $ \left( { - 1} \right)^{\tfrac{{5^2 k^2 - 30k}} {8}} = 1 $ and for this to happen: $ \left. {16} \right|\left[ {k\left( {5k - 6} \right)} \right] $ so k must be even, and then: $ k = 2k_1 $ and we must have: $ \left. 4 \right|\left[ {k_1 \left( {5k_1 - 3} \right)} \right] $ and for this either: $ \left. 4 \right|k_1 $ or $ 5k_1 \equiv k_1 \equiv 3\left( {\bmod .4} \right) \Rightarrow k_1 = 4k_2 + 3 $ then we must have ( substitute back to p): $ p \equiv 37\left( {\bmod .40} \right) \vee p \equiv 27\left( {\bmod .40} \right) $
Case $p=5k+3$ here we get: $ p \equiv -37\left( {\bmod .40} \right) \vee p \equiv -27\left( {\bmod .40} \right) $ -check it-

So the solution is the set of all primes $p$ satisfying one of the following congruences: $ p \equiv \pm 1, \pm 27, \pm 31, \pm 37\left( {\bmod .40} \right) $

**ThePerfectHacker** · April 14th 2009, 09:54 PM

Originally Posted by mancillaj3

Find all primes p such that $(\frac{10}{p})=1$

Here is an alternate approach but not much of a difference.

First, $(10/p) = (2/p)(5/p)$ therefore, $(2/p)=(5/p)=1\text{ or }(2/p)=(5/p)=-1$ .

You should know that $(2/p) = 1$ iff $p\equiv 1,7(\bmod 8)$ .

Now $(5/p) = (p/5)$ (since $5\equiv 1(\bmod 4)$ ).
If $p\equiv 1,4(\bmod 5) \implies (p/5) = (\pm 1/5) = 1$ .
If $p\equiv 2,3(\bmod 5)\implies (p/5) = (\pm 2/5) = -1$ .
Thus, $(5/p) = 1$ iff $p\equiv 1,4(\bmod 5)$ .

Hence, $(2/p)=(5/p)=1$ iff:
$p\equiv 1(\bmod 5) \text{ and }p\equiv 1(\bmod 8)$
$p\equiv 1(\bmod 5) \text{ and }p\equiv -1(\bmod 8)$
$p\equiv -1(\bmod 5)\text{ and }p\equiv 1(\bmod 8)$
$p\equiv -1(\bmod 5)\text{ and }p\equiv -1(\bmod 8)$
Solving this:
$p\equiv \pm 1, \pm 31(\bmod 40)$

Do same computation for the second part, I am too lazy to write all the details.

Thread: Find all primes p such that [math]\frac{10}{p}[/math]=1.

LinkBack

Thread Tools

Display

Find all primes p such that (10/p)=1.

Similar Math Help Forum Discussions

How do I solve this [math] \int_\frac{pi}{2}^0 \frac{cosx}{1 + sin^2x} dx[/math]?

If [math]y = In \left[ \frac{x(x^2 + 1)}{\sqrt{x^3 - 1}} \right] [/math]

Finding the [MATH][/MATH] tags generator button in post menu??

Find the radius of convergence for the power series [MATH][/MATH] n=1, infinite (2x+1

find [MATH]\alpha , \beta[/MATH]

Search Tags