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

p1, p2 mod q^2

Expand Messages
  • Kermit Rose
    If 0
    Message 1 of 2 , Oct 2, 2011
    • 0 Attachment
      If 0 < b1 < p1 < q
      and 0 < b2 < p2 < q

      and

      b1^p1 = 1 mod q^2

      and
      b2^p2 = 1 mod q^2


      What can we conclude about relation between p1 and p2?

      Consider the case where q is prime.

      It must also be true that

      b1^p1 = 1 mod q
      and
      b2^p2 = 1 mod q.

      and since q is prime, p1 divides (q-1) and
      p2 divides (q-1).

      If p1 is not equal to p2, then it must be that

      p1*p2 divides (q-1).

      which means that q would have to be much larger, perhaps out of bounds
      of calculation.

      Kermit
    • djbroadhurst
      ... Indeed. Moreover, (b1,q) and (b2,q) are Wieferich pairs with the same q. Such conjunctions are rare. Even when we find one, the probability that it solves
      Message 2 of 2 , Oct 2, 2011
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        Kermit Rose <kermit@...> wrote:

        > b1^p1 = 1 mod q^2
        > b2^p2 = 1 mod q^2

        > If p1 is not equal to p2, then it must be that
        > p1*p2 divides (q-1).

        Indeed. Moreover, (b1,q) and (b2,q) are Wieferich pairs
        with the same q. Such conjunctions are rare.
        Even when we find one, the probability that it solves
        our problem, with p2 > p1 > 2, is low.
        If q = 2*k*p1*p2 + 1, we might guess the probability as

        (p1/(q-1))*(p2/(q-1)) = 1/(2*k*(q-1))

        which is why this feat has not yet been accomplished.
        But that does not mean that it cannot be done.

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.