1. ## Pollard p-1

Let $\displaystyle d_n = (2^{n!} - 1, m)$
Explain why $\displaystyle d_n \mid d_{n+1}$ for n = 1,2,...
Show that $\displaystyle d_n > 1$ if m has a prime factor p such that $\displaystyle (p-1) \mid n!$.

My idea is to show that $\displaystyle (2^{n!}-1,m)$ can only equal factors of m, and since $\displaystyle d_n and d_{n+1}$ have the same m in the gcd and that $\displaystyle d_n < d_{n+1}$, $\displaystyle d_n \mid d_{n+1}$.
I don't think this reasoning is rigorous.
Also, I have trouble with showing that $\displaystyle d_n > 1$ if m has a prime factor p such that $\displaystyle (p-1) \mid n!$

Thanks!

2. Notice that if m devides n, then for any positive integer a, we have $\displaystyle a^m-1\text{ devides }a^n-1$.
(1)$\displaystyle d_n$ is a common divisor of m and $\displaystyle 2^{(n+1)!}-1$,since $\displaystyle 2^{n!}-1\text{ devides }2^{(n+1)!}-1$.
thus $\displaystyle d_n\text{ divides }d_{n+1}$.
(2) if we show that p divides $\displaystyle 2^{n!}-1$, then the proposition is proved.
since p-1 divides n!, there exist positive integer k such that n!=(p-1)k.
and
$\displaystyle 2^{n!}-1=(2^{p-1}-1)(1+2^{p-1}+\cdot \cdot \cdot +2^{(k-1)(p-1)})$
combined with Fermat's theorem "$\displaystyle p\text{ divides }2^{p-1}-1$" gives "$\displaystyle p\text{ divides }2^{n!}-1$".