Exercise 2.4.15 (Lemma for Pollard $p-1$ method)

Question

Show that if $(a,m)=1$ and $m$ has a prime factor $p$ such that $(p-1) \mid Q$, then $(a^Q - 1,m)>1$.

Richard Ganaye · Accepted Answer

\begin{proof} 
Since $a\wedge m = 1$, and $p\mid m$, then $a\wedge p = 1$. By Fermat's theorem, $a^{p-1} \equiv 1 \pmod p$.

The hypothesis $p-1 \mid Q$ show that $Q = k (p-1)$ for some integer $k$. Then $$a^Q = (a^{p-1})^k \equiv 1 \pmod p.$$ So $p \mid a^Q - 1$ and $p \mid m$, therefore $p \mid (a^Q - 1) \wedge m$. This shows that
$$(a^Q - 1) \wedge m >1.$$
\end{proof}

Exercise 2.4.15 (Lemma for Pollard $p-1$ method)

Answers

Comments

Exercise 2.4.15 (Lemma for Pollard $p-1$ method)

Answers

Comments

Add answer