Loading ...
Sorry, an error occurred while loading the content.
 

Re: Thanks to all. Proposed binary Prime number test fails.

Expand Messages
  • elevensmooth
    ... Yes. Let d be the smallest value so that p divides b^d-1. First observe that if b^x-1 and b^y-1 and both divisible by p^2 (or any other number), then
    Message 1 of 18 , Jun 5, 2007
      --- In primenumbers@yahoogroups.com, "Kevin Acres" <research@...> wrote:

      > just wondering ...
      > if it holds true that p^2 always divides the
      > minimal base^(p-1/x)-1 that p does.

      Yes. Let d be the smallest value so that p divides b^d-1.

      First observe that if b^x-1 and b^y-1 and both divisible by p^2 (or
      any other number), then b^(gcd(x,y))-1 is also divisible by p^2 (or
      any other number).

      Second, observe that b^(pd)-1 is divisible by p^2. To see this,
      express b^d as (ps+1), then expand (ps+1)^p with the binomial theorem.

      Third, observe that every case of divisibility by p is of the form
      b^(kd)-1, and every case of divisibility by p^2 is also a case of
      divisiblity by p, so the minimal case of divisibility by p^2 must be
      of the form b^(kd)-1.

      Finally, if there is any k<p such that b^(kd)-1 is divisible by p^2,
      then b^gcd(kd,pd) must also be divisible by p^2, but gcd(kd,pd)=d.

      Therefore, in all cases of Vanishing Fermat Quotients, p^2 divides the
      same primitive term that p divides.

      William
      Poohbah of OddPerfect.org

      P.S. We still need a few large factors of Vanishing Fermat Quotients
      at http://oddperfect.org/FermatQuotients.html
    • mistermac39
      Earlier, with reference to 29, and 47 the number 61 came up. It is a factor of the 15th Fibonacci number 610 Ring any bells?
      Message 2 of 18 , Jun 14, 2007
        Earlier, with reference to 29, and 47 the number 61 came up.

        It is a factor of the 15th Fibonacci number 610

        Ring any bells?
      Your message has been successfully submitted and would be delivered to recipients shortly.