## k-generalized Carmichael numbers

Expand Messages
• 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.]
• ... http://alumnus.caltech.edu/~however/talks/FortCollins.pdf David
Message 2 of 6 , Dec 12, 2012
• 0 Attachment
"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
• ... http://oeis.org/A175531 gives an update David
Message 3 of 6 , Dec 12, 2012
• 0 Attachment

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
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.
• ... 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
"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

It is easy to construct larger solutions. For example
provides a link to 246 solutions in
with n = 1 mod p^2-1, for each prime p|n.
For 144153 such solutions, see the 12 MB file
obtained by Robert Gerbicz on 1 April 2009

David
• 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.