# Intro to modern algebra proof questions

1. Jul 2, 2010

### rg2004

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. Jul 2, 2010

### Staff: Mentor

What does |2|n mean?

3. Jul 2, 2010

### rg2004

the "order of 2 mod n"

for the smallest x such that:
2x=1 (mod n)
where x=|2|n

4. Jul 2, 2010

### 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 $\equiv$ 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 $\equiv$ 1 (mod 3)
or
p $\equiv$ 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).

5. Jul 2, 2010

### snipez90

For the first one, have you considered Fermat's Little Theorem?

6. Jul 2, 2010

### tmccullough

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. $$a^b\equiv 1 (\textrm{mod}\;n).$$

Note that $$2^p \equiv -1 (\textrm{mod}\;n) \Longrightarrow 2^{2p} \equiv 1 (\textrm{mod}\;n)$$. 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 $$a^{p-1} \equiv 1 (\textrm{mod}\;p)$$. From what they tell you, you see that $$a^3\equiv 1 (\textrm{mod}\;p).$$ Either the order of a mod p is 1 (a=1) or 3. It can't be 1, because $$a^2+a+1 \equiv 0 (\textrm{mod}\;p)$$ and $$p>3$$. Then, (p-1) is divisible by 3.