Intro to modern algebra proof questions

[rg2004]

Ive been working all afternoon on these two problems, and i don't have a clue how to solve either of them.

Homework Statement

Let p>2 be a prime number and let n=2^p +1. Prove that |2|_n =2p.

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

Homework Equations

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

The Attempt at a Solution

i don't even know where to begin, everything I've done ends with dead ends

 

[Mark44]

Ive been working all afternoon on these two problems, and i don't have a clue how to solve either of them.

Homework Statement

Let p>2 be a prime number and let n=2^p +1. Prove that |2|_n =2p.

What does |2|_n mean?

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

Homework Equations

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

The Attempt at a Solution

i don't even know where to begin, everything I've done ends with dead ends

 

[rg2004]

the "order of 2 mod n"

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

 

[Mark44]

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.

a² + a + 1 $\equiv$ 0 (mod p) so what does that imply about a³ - 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).

 

[snipez90]

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

 

[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).$$

Homework Statement

Let p>2 be a prime number and let n=2^p +1. Prove that |2|_n =2p.

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.

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

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.