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

k-generalized Carmichael numbers

Expand Messages
  • WarrenS
    It seems the following concept ought to be important: k-Generalized Carmichael numbers. DEFINITION: If N is composite and squarefree and: for all primes p
    Message 1 of 6 , Dec 12, 2012
    • 0 Attachment
      It seems the following concept ought to be important:
      "k-Generalized Carmichael numbers."

      DEFINITION:
      If N is composite and squarefree and:
      for all primes p that divide N,
      p-1 happens to divide N-1,
      and:
      for each j=2,3,4,...,k-1,
      for all primes p that divide N,
      (p^j-1)/(p-1)
      happens to divide (N^j-1)/(N-1),
      then call N a "k-generalized Carmichael number."

      If you make k large enough as a function of N, then I guess
      k-generalized Carmichael numbers must stop existing.
      QUESTION: how large do you need?
      As an initial guess, if k>(logN)*(some positive constant)
      that is enough to stop N from being a
      k-Generalized Carmichael number.

      QUESTION:
      Can you find any k-generalized Carmichaels for k=2,3 or 4?
      [I believe my computer showed none exist when N<10^16.]
    • djbroadhurst
      ... http://alumnus.caltech.edu/~however/talks/FortCollins.pdf David
      Message 2 of 6 , Dec 12, 2012
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "WarrenS" <warren.wds@...> wrote:

        > It seems the following concept ought to be important:
        > "k-Generalized Carmichael numbers."

        http://alumnus.caltech.edu/~however/talks/FortCollins.pdf

        David
      • djbroadhurst
        ... http://oeis.org/A175531 gives an update David
        Message 3 of 6 , Dec 12, 2012
        • 0 Attachment
          --- In primenumbers@yahoogroups.com,
          "djbroadhurst" <d.broadhurst@...> wrote:

          > http://alumnus.caltech.edu/~however/talks/FortCollins.pdf

          http://oeis.org/A175531 gives an update

          David
        • WarrenS
          ... --None of the three numbers listed in http://oeis.org/A175531 qualifies as a 2-generalized Carmichael number by my definition. Howe s definition on page
          Message 4 of 6 , Dec 12, 2012
          • 0 Attachment
            > > http://alumnus.caltech.edu/~however/talks/FortCollins.pdf
            >
            > http://oeis.org/A175531 gives an update
            >
            > David

            --None of the three numbers listed in http://oeis.org/A175531
            qualifies as a "2-generalized Carmichael number" by my definition.

            Howe's definition on page 16 of his lecture slides is different from
            and I'm not even sure it is related to mine.
            I don't understand Howe's motivation, although I guess it must be
            spiritually similar to mine.

            I suspect a 2-generalized Carmichael exists with N<10^100.
          • djbroadhurst
            ... Yes. His was more interesting to me, in the context of pseudoprimality: https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1006&L=nmbrthry&T=0&F=&S=&P=51
            Message 5 of 6 , Dec 12, 2012
            • 0 Attachment
              --- In primenumbers@yahoogroups.com,
              "WarrenS" <warren.wds@...> wrote:
              > Howe's definition on page 16 of his lecture slides is different

              Yes. His was more interesting to me, in the context
              of pseudoprimality:

              https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1006&L=nmbrthry&T=0&F=&S=&P=51

              http://tech.groups.yahoo.com/group/primenumbers/message/21461

              It is easy to construct larger solutions. For example
              http://tech.groups.yahoo.com/group/primenumbers/message/19971
              provides a link to 246 solutions in
              http://physics.open.ac.uk/~dbroadhu/cert/erdos2.out
              with n = 1 mod p^2-1, for each prime p|n.
              For 144153 such solutions, see the 12 MB file
              http://physics.open.ac.uk/~dbroadhu/cert/carmrob2.txt
              obtained by Robert Gerbicz on 1 April 2009

              David
            • WarrenS
              Ouch, there was a typo in the definition. Here is the message back again with typo corrected (k-1 changed to k): It seems the following concept ought to be
              Message 6 of 6 , Dec 12, 2012
              • 0 Attachment
                Ouch, there was a typo in the definition. Here is the message back again
                with typo corrected (k-1 changed to k):

                It seems the following concept ought to be important:
                "k-Generalized Carmichael numbers."

                DEFINITION:
                If N is composite and squarefree and:
                for all primes p that divide N,
                p-1 happens to divide N-1,
                and:
                for each j=2,3,4,...,k,
                for all primes p that divide N,
                (p^j-1)/(p-1)
                happens to divide (N^j-1)/(N-1),
                then call N a "k-generalized Carmichael number."

                If you make k large enough as a function of N, then I guess
                k-generalized Carmichael numbers must stop existing.
                QUESTION: how large do you need?
                As an initial guess, if k>(logN)*(some positive constant)
                that is enough to stop N from being a
                k-Generalized Carmichael number.

                QUESTION:
                Can you find any k-generalized Carmichaels for k=2,3 or 4?
                [I believe my computer showed none exist when N<10^16.]
              Your message has been successfully submitted and would be delivered to recipients shortly.