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.