1. ## cyclic groups

I have a problem in a textbook that is giving me trouble. Either I'm missing something or there is some sort of mistake in the question. The problem is with part (ii), the other parts seem okay, but I'll post all parts anyway:

Let $\displaystyle p = 2^k +1$ be a prime number, and let $\displaystyle G$ be the group of integers $\displaystyle 1, 2, \ldots, p-1$, with multiplication modulo $\displaystyle p$.

(i) Show that if $\displaystyle 0 < m < k$ then $\displaystyle 0 < 2^m -1 < p$ and deduce that $\displaystyle 2^m \neq 1 \mod p$.

(ii) Show that if $\displaystyle k< m < 2k$ then $\displaystyle 2^m = 1 \mod p \Longrightarrow 2^{2k-m} = -1 \mod p$ and decude that $\displaystyle 2^m \neq 1 \mod p$

(iii) Use parts (i) and (ii) to show that the order of the element 2 in $\displaystyle G$ is $\displaystyle 2k$

(iv) Decude that $\displaystyle k$ is a power of 2.

(ii) Show that if $\displaystyle k< m < 2k$ then $\displaystyle 2^m = 1 \mod p \Longrightarrow 2^{2k-m} = -1 \mod p$ and decude that $\displaystyle 2^m \neq 1 \mod p$
Note that $\displaystyle 5=2^2+1$ thus, $\displaystyle k=2$ note that,
$\displaystyle 2=k<m=3<4=2k$ but, $\displaystyle 2^3=1 \mbox{ mod } 5$ is not true

3. (ii) Show that if $\displaystyle k< m < 2k$ then $\displaystyle 2^m = 1 \mod p \Longrightarrow 2^{2k-m} = -1 \mod p$ and decude that $\displaystyle 2^m \neq 1 \mod p$
it doesn't mean 'then $\displaystyle 2^m = 1 \mod p$ is always true'
it means that if this is true for $\displaystyle m$ in $\displaystyle k<m<2k$, then it implies that $\displaystyle 2^{2k-m} = -1 \mod p$. (atleast that is my interpretation of the question)

4. If p =2^k+1 then 2^k == -1 mod p. If we assume 2^m == 1 mod p with k < m < 2k, then 2^{2k-m} == (-1)^2.(1) == 1 mod p. But 0 < 2k-m < k and by (i) that's impossible. I think there's a sign error in the statement of (ii).

5. Originally Posted by rgep
If p =2^k+1 then 2^k == -1 mod p. If we assume 2^m == 1 mod p with k < m < 2k, then 2^{2k-m} == (-1)^2.(1) == 1 mod p. But 0 < 2k-m < k and by (i) that's impossible. I think there's a sign error in the statement of (ii).
ie that it should say 1 instead of -1?

6. Quite so.