Pollard p-1

**bictory** · December 14th 2009, 05:45 PM

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!

**Shanks** · December 14th 2009, 07:09 PM

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

Thread: Pollard p-1

LinkBack

Thread Tools

Display

Pollard p-1

Similar Math Help Forum Discussions

Cryptography -- Pollard p-1 Algorithm in Mathematica

[SOLVED] Tenenbaum and Pollard, Problem 2.10.6

Pollard rho algorithm

Pollard Rho Algorithm

Search Tags