Results 1 to 3 of 3

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

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    40

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

    Find all primes p such that (\frac{10}{p})=1
    Last edited by mancillaj3; April 14th 2009 at 12:40 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    First: <br />
\left( {\tfrac{{10}}<br />
{p}} \right)_L  = \left( {\tfrac{2}<br />
{p}} \right)_L  \cdot \left( {\tfrac{5}<br />
{p}} \right)_L <br /> <br />

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

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

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

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

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

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


    So the solution is the set of all primes p satisfying one of the following congruences: <br />
p \equiv  \pm 1, \pm 27, \pm 31, \pm 37\left( {\bmod .40} \right)<br />
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by mancillaj3 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: March 26th 2011, 06:05 AM
  2. Replies: 3
    Last Post: March 26th 2011, 05:43 AM
  3. Replies: 1
    Last Post: June 19th 2010, 10:05 PM
  4. Replies: 1
    Last Post: June 2nd 2010, 09:49 AM
  5. find [MATH]\alpha , \beta[/MATH]
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: December 23rd 2009, 03:43 AM

Search Tags


/mathhelpforum @mathhelpforum