1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    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


    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)
    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