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

Factorisation of Carmichael numbers

Expand Messages
  • mikeoakes2
    By inspection of a list of the first few Carmichael numbers, e.g. http://www.kobepharma-u.ac.jp/~math/notes/note02.html I have come to the following
    Message 1 of 7 , May 27, 2010
    • 0 Attachment
      By inspection of a list of the first few Carmichael numbers, e.g.
      http://www.kobepharma-u.ac.jp/~math/notes/note02.html
      I have come to the following

      Conjecture: If n is a Carmichael number divisible by 3,
      then all the other prime factors of n are congruent to 5 mod 6.

      Does anyone know whether this result is well-known - or even true?
      There doesn't seem to be an obvious proof.

      Mike
    • djbroadhurst
      ... There are 1967 Carmichael numbers less than 10^18 that are divisible by 3 and your conjecture holds for all of them. David
      Message 2 of 7 , May 27, 2010
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "mikeoakes2" <mikeoakes2@...> wrote:

        > Conjecture: If n is a Carmichael number divisible by 3,
        > then all the other prime factors of n are congruent to 5 mod 6.

        There are 1967 Carmichael numbers less than 10^18 that
        are divisible by 3 and your conjecture holds for all of them.

        David
      • Jack Brennen
        Well, if a Carmichael number C is divisible by both 3 and a prime of the form 6n+1, then you have a problem with fulfilling: a^C == a (modulo 6n+1) If a is a
        Message 3 of 7 , May 27, 2010
        • 0 Attachment
          Well, if a Carmichael number C is divisible by both 3 and a prime
          of the form 6n+1, then you have a problem with fulfilling:

          a^C == a (modulo 6n+1)

          If a is a non-cubic-residue modulo 6n+1, this obviously can't
          work, and note that all primes of the form 6n+1 have non-cubic-residues.

          I think that's the outline of a proof -- I know I'm handwaving a little,
          but I think you could fill in the blanks.

          mikeoakes2 wrote:
          > By inspection of a list of the first few Carmichael numbers, e.g.
          > http://www.kobepharma-u.ac.jp/~math/notes/note02.html
          > I have come to the following
          >
          > Conjecture: If n is a Carmichael number divisible by 3,
          > then all the other prime factors of n are congruent to 5 mod 6.
          >
          > Does anyone know whether this result is well-known - or even true?
          > There doesn't seem to be an obvious proof.
          >
          > Mike
          >
          >
          >
          >
          > ------------------------------------
          >
          > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          > The Prime Pages : http://www.primepages.org/
          >
          > Yahoo! Groups Links
          >
          >
          >
          >
          >
        • maximilian_hasler
          If a Carmichael number n has a prime divisor p = 6k+1, then, since p-1 | n-1 (Korselt s criterion, cf. Wikipedia) we have that 6k | n-1, such that n = 1 (mod
          Message 4 of 7 , May 27, 2010
          • 0 Attachment
            If a Carmichael number n has a prime divisor p = 6k+1,
            then, since p-1 | n-1 (Korselt's criterion, cf. Wikipedia)
            we have that 6k | n-1, such that n = 1 (mod 3).

            This means that a Carmichael number cannot be divisible by 3 if it has a prime factor p = 1 (mod 6).

            Therefore, if 3 | n, then it cannot have a prime divisor = 1 mod 6.

            Maximilian


            --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
            >
            >
            >
            > --- In primenumbers@yahoogroups.com,
            > "mikeoakes2" <mikeoakes2@> wrote:
            >
            > > Conjecture: If n is a Carmichael number divisible by 3,
            > > then all the other prime factors of n are congruent to 5 mod 6.
            >
            > There are 1967 Carmichael numbers less than 10^18 that
            > are divisible by 3 and your conjecture holds for all of them.
            >
            > David
            >
          • mikeoakes2
            ... Thanks for such a speedy verification. Now, based more on intuition than much experimental evidence, here is another Conjecture: If n is a Carmichael
            Message 5 of 7 , May 27, 2010
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
              >
              > --- In primenumbers@yahoogroups.com,
              > "mikeoakes2" <mikeoakes2@> wrote:
              >
              > > Conjecture: If n is a Carmichael number divisible by 3,
              > > then all the other prime factors of n are congruent to 5 mod 6.
              >
              > There are 1967 Carmichael numbers less than 10^18 that
              > are divisible by 3 and your conjecture holds for all of them.

              Thanks for such a speedy verification.

              Now, based more on intuition than much experimental evidence, here is another

              Conjecture: If n is a Carmichael number divisible by 3, and p is any other prime factor, so that by definition (p-1) divides (n-1), then (p+1) never divides (n^2-1).

              Mike
            • djbroadhurst
              ... Thanks, Maximilian! This means that Mike will not have to write to a civil servant at 2 Eldon Road, Cheltenham, Glos GL52 6TU, UK, asking whether this is
              Message 6 of 7 , May 27, 2010
              • 0 Attachment
                --- In primenumbers@yahoogroups.com,
                "maximilian_hasler" <maximilian.hasler@...> wrote:

                > If a Carmichael number n has a prime divisor p = 6k+1,
                > then, since p-1 | n-1 (Korselt's criterion, cf. Wikipedia)
                > we have that 6k | n-1, such that n = 1 (mod 3).
                > This means that a Carmichael number cannot be divisible by 3 if
                > it has a prime factor p = 1 (mod 6).
                > Therefore, if 3 | n, then it cannot have a prime divisor = 1 mod 6.

                Thanks, Maximilian!

                This means that Mike will not have to write to a "civil servant" at
                2 Eldon Road, Cheltenham, Glos GL52 6TU, UK,
                asking whether this is an "official secret" in the UK :-)

                David
              • mikeoakes2
                ... Doh! (Is an immediate corollary of the first conjecture, proved so elegantly by Maximilian.) Mike
                Message 7 of 7 , May 27, 2010
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
                  >
                  > Conjecture: If n is a Carmichael number divisible by 3, and p is any other prime factor, so that by definition (p-1) divides (n-1), then (p+1) never divides (n^2-1).

                  Doh!
                  (Is an immediate corollary of the first conjecture, proved so elegantly by Maximilian.)

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