# Let $m=2^{17}-1$, and suppose that $p$ is a prime factor of $m$.

$(a)$ Deduce that 17 divides p-1

$(b)$ Deduce that $p$ must be of the form $34k+1$ for some positive integer $k$.

In an earlier part of the question I showed that $2^{17}\equiv 1$ (mod p). In lectures I have learnt Fermat's Little Theorem and the Fermat-Euler Theorem but I'm not sure how exactly I do $(a)$ using these. Using $(a)$ we have that $p=17a+1$ for some positive integer $a$, I presume that since $m+1$ is a power of $2$ that is why it is $34$?

• $p=17a+1$ for some $a$. If $a$ was odd, then $17a+1$ would be even, impossible. So $a$ is even, say $a=2k$. – André Nicolas Mar 19 '15 at 0:41

## 2 Answers

The group of units modulo $p$ has order $p-1$ and the order of $2$ mod. $p$ is $17$. By Lagrange's theorem, $17$ divides $p-1$. Observe $p$ is odd because $m$ is odd, so that $2$ divides $p-1$, hence $2\cdot 17=34$ divides $p-1$. The conclusion follows.

$a)$

Fermat-Little Theorem states that: for $(a,p) = 1 \to a^{p-1} = 1 \pmod p$. Since $p\mid 2^{17}-1$ which is an odd number, $p \neq 2$, and thus $(2,p) = 1 \to 2^{p-1} = 1 \pmod p$. Consider the multiplicative group $\mathbb{Z_{p}}^{*}$, then the order of $2$ which is $17$ must divide the order of the group which is $p-1$. Thus $17\mid p-1$.

$b)$ You can follow the hint above.