Results 1 to 2 of 2

Math Help - Pollard p-1

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    15

    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!
    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 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".
    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: April 8th 2011, 11:53 AM
  2. [SOLVED] Tenenbaum and Pollard, Problem 2.10.6
    Posted in the Differential Equations Forum
    Replies: 10
    Last Post: March 4th 2011, 05:27 PM
  3. Pollard rho algorithm
    Posted in the Math Software Forum
    Replies: 0
    Last Post: November 26th 2009, 07:37 PM
  4. Pollard Rho Algorithm
    Posted in the Math Software Forum
    Replies: 0
    Last Post: November 10th 2009, 10:17 AM

Search Tags


/mathhelpforum @mathhelpforum