0
$\begingroup$

$(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$?

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

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.