# Math Help - Pollard p-1

1. ## Pollard p-1

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

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

Thanks!

2. Notice that if m devides n, then for any positive integer a, we have $a^m-1\text{ devides }a^n-1$.
(1) $d_n$ is a common divisor of m and $2^{(n+1)!}-1$,since $2^{n!}-1\text{ devides }2^{(n+1)!}-1$.
thus $d_n\text{ divides }d_{n+1}$.
(2) if we show that p divides $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
$2^{n!}-1=(2^{p-1}-1)(1+2^{p-1}+\cdot \cdot \cdot +2^{(k-1)(p-1)})$
combined with Fermat's theorem " $p\text{ divides }2^{p-1}-1$" gives " $p\text{ divides }2^{n!}-1$".