Results 1 to 2 of 2

Thread: Pollard p-1

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    15

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    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$".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cryptography -- Pollard p-1 Algorithm in Mathematica
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 8th 2011, 11:53 AM
  2. [SOLVED] Tenenbaum and Pollard, Problem 2.10.6
    Posted in the Differential Equations Forum
    Replies: 10
    Last Post: Mar 4th 2011, 05:27 PM
  3. Pollard rho algorithm
    Posted in the Math Software Forum
    Replies: 0
    Last Post: Nov 26th 2009, 07:37 PM
  4. Pollard Rho Algorithm
    Posted in the Math Software Forum
    Replies: 0
    Last Post: Nov 10th 2009, 10:17 AM

Search Tags


/mathhelpforum @mathhelpforum