Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Intro to modern algebra proof questions

  1. Jul 2, 2010 #1
    Ive been working all afternoon on these two problems, and i dont have a clue how to solve either of them.

    1. The problem statement, all variables and given/known data
    Let p>2 be a prime number and let n=2p +1. Prove that |2|n =2p.

    Let p > 3 be a prime number and suppose there is an integer a such that a2+a+1 ≡ 0 (mod p).
    Prove that p≡1 (mod 3). (Hint: a3 −1=(a2 +a+1)(a−1))

    2. Relevant equations

    phi(x)=phi(p1)*phi(p2)...phi(pn) where p are the unique prime factors of x

    3. The attempt at a solution

    i dont even know where to begin, everything ive done ends with dead ends
     
  2. jcsd
  3. Jul 2, 2010 #2

    Mark44

    Staff: Mentor

    What does |2|n mean?
     
  4. Jul 2, 2010 #3
    the "order of 2 mod n"

    for the smallest x such that:
    2x=1 (mod n)
    where x=|2|n
     
  5. Jul 2, 2010 #4

    Mark44

    Staff: Mentor

    I've put in about a half-hour on #2 and it doesn't occur to me how to prove it, but here are some things to think about.

    a2 + a + 1 [itex]\equiv[/itex] 0 (mod p) so what does that imply about a3 - 1 (keeping the hint in mind)?

    In modulo 3 equivalence classes, there really are only two choices for p:
    p [itex]\equiv[/itex] 1 (mod 3)
    or
    p [itex]\equiv[/itex] 2 (mod 3)

    p can't be equivalent to 0 (mod 3) or it would be a multiple of 3, hence nonprime (3 * 1 is prime, but need not be considered, since it's given that p > 3).
     
  6. Jul 2, 2010 #5
    For the first one, have you considered Fermat's Little Theorem?
     
  7. Jul 2, 2010 #6
    There is a simple underlying fact that will help you complete both. This is fundamental enough that I don't think it has a name. Remember that the order of a mod n divides any b s.t. [tex]a^b\equiv 1 (\textrm{mod}\;n).[/tex]

    Note that [tex] 2^p \equiv -1 (\textrm{mod}\;n) \Longrightarrow 2^{2p} \equiv 1 (\textrm{mod}\;n)[/tex]. Then, the order of 2 mod n divides 2p. It can't be 2 or p, so it must be 2p.

    As snipez90 suggested, you know from Fermat's little theorem that [tex]a^{p-1} \equiv 1 (\textrm{mod}\;p)[/tex]. From what they tell you, you see that [tex]a^3\equiv 1 (\textrm{mod}\;p).[/tex] Either the order of a mod p is 1 (a=1) or 3. It can't be 1, because [tex]a^2+a+1 \equiv 0 (\textrm{mod}\;p)[/tex] and [tex]p>3[/tex]. Then, (p-1) is divisible by 3.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook