# Continual Learning with Deep Streaming Regularized Discriminant Analysis

Joe Khawand 1,2 Peter Hanappe 2

1 Ecole Polytechnique
2 Sony Computer Science Laboratories Paris
<EMAIL_ADDRESS>David Colliaux 2

###### Abstract

Continual learning is increasingly sought after in real-world machine learning
applications, as it enables learning in a more human-like manner. Conventional
machine learning approaches fail to achieve this, as incrementally updating
the model with non-identically distributed data leads to catastrophic
forgetting, where existing representations are overwritten. Although
traditional continual learning methods have mostly focused on batch learning,
which involves learning from large collections of labeled data sequentially,
this approach is not well-suited for real-world applications where we would
like new data to be integrated directly. This necessitates a paradigm shift
towards streaming learning. In this paper, we
propose111https://github.com/SonyCSLParis/Deep_SRDA.git a streaming version of
regularized discriminant analysis as a solution to this challenge. We combine
our algorithm with a convolutional neural network and demonstrate that it
outperforms both batch learning and existing streaming learning algorithms on
the ImageNet ILSVRC-2012 dataset.

##  1 Introduction

Continual learning, also known as lifelong learning, refers to the ability of
a learning system to sequentially acquire and adapt knowledge over time. This
type of learning mimics animal learning [8] and is increasingly sought after
in various domains such as medical diagnostics [22], autonomous vehicles [40],
and finance [35], where the learner needs to continually adapt to changing
data. The major challenge in continual learning is the phenomenon of
catastrophic forgetting [9, 31]. It refers to the situation where a naively
incrementally trained deep neural network forgets previously learned
representations to specialise to the new task at hand.

Traditionally, the bulk of research [45] in continual learning has primarily
concentrated on batch learning approaches, which process data in fixed
batches. In this setting, a continual learner typically iterates multiple
times over the given task in an offline manner, allowing them to achieve
satisfactory performance. However, this approach requires storing all data
from the current task for training, which is not suitable for on-device
learning.

As a result, recent research has emerged in the field of Online Continual
learning [27], where data arrives in small, incremental batches and previously
seen batches from the current or previous tasks are no longer accessible.
Therefore, a model must effectively learn from a single pass over the online
data stream, even when encountering new classes (Online Class Incremental,
OCI) or data non-stationarity, such as new background, blur, noise,
illumination, and occlusion (Online Domain Incremental, ODI).

Figure 1: Deep SRDA model diagram.

We take this scenario one step further and consider a streaming case of the
online continual learning scenario, where a learner learns from batches of
size 1. This particular case of Streaming learning aims to develop
methodologies that can efficiently learn from streaming data, enabling
continuous adaptation without relying on complete batches. Specifically, we
concentrate on the application of classification in computer vision, focusing
on the general scenario of Online Class Incremental.

In this paper, we aim to contribute to the field of continual learning by
proposing a novel approach called Deep Streaming Regularized Discriminant
Analysis (SRDA). Building upon the foundations of Deep Streaming Linear
Discriminant Analysis (SLDA) [14], our method combines SLDA with a streaming
version of Quadratic Discriminant Analysis (QDA) to achieve state-of-the-art
performance. As done in [14], we combine our model with a convolutional neural
network (CNN) and empirically demonstrate its superiority over the other
streaming and batch learning methods on the ImageNet ILSVRC-2012 dataset [39].
To the best of our knowledge, this use of a regularized discriminant analysis
method with a neural network represents a novel contribution that has not been
explored before.

This paper makes the following contributions:

  1. 1.

We present the SQDA and SRDA algorithms. We show that SQDA does not generalize
to high dimensional problems and present SRDA as a solution.

  2. 2.

We demonstrate that SRDA outperforms state-of-the-art streaming and continual
learning algorithms.

##  2 Related work

###  2.1 Continual Learning

Continual learning addresses the challenges of catastrophic forgetting that
occur when training a model incrementally, breaking the usual i.i.d.
assumption on the training data. This problem arises from the plasticity
dilemma [1] and has been heavily studied in recent years [45]. Various
continual learning scenarios have been developed to continually train models,
with the three main ones being task incremental, class incremental, and domain
incremental.

In the task incremental setting, different training steps are identified by a
label. Models trained in this setting tend to perform well because there is an
indication of the task in the data. However, this scenario is not very
realistic as real-world data is not typically labelled by tasks. The class
incremental scenario considers the real-world scenario of adding new classes
without any task delimiters. Lastly, in the domain incremental scenario, the
focus is on dealing with the addition of new domains or changing environments
without any explicit task labels.

To mitigate catastrophic forgetting, several methods have been employed. The
main ones include regularization [26, 44, 20, 49, 3, 23], rehearsal or pseudo-
rehearsal [38, 41, 37], combined [18, 5, 24], and architectural [29, 25].
Notably, the rehearsal and pseudo-rehearsal categories have shown the most
promising results. In these approaches, the learner stores previously
encountered samples in a buffer for future training [38]. In some instances,
pseudo-rehearsal techniques explore the replacement of the buffer with a
generative model [41, 37].

###  2.2 Online Continual Learning

Online continual learning is a more challenging subset of continual learning
where data arrives in an online fashion one tiny batch at a time and
previously encountered batches are not accessible. This field builds upon
existing methods for continual learning while adding specific tricks to tackle
this scenario. In this online setting, recent works [30, 16, 47, 2, 27] have
shown that the Softmax layer and its associated Fully-Connected layer suffer
from task-recency bias, where those layers tend to be biased to the last
encountered classes. This has prompted the creation of multiple tricks to
alleviate this problem. One example is the application of various tricks in
replay-based scenarios:

  * •

Labels Trick [50]: Cross-entropy loss calculation considers only the classes
present in the mini-batch, preventing excessive penalization of logits for
classes absent from the mini-batch.

  * •

Multiple Iterations [4]: A single mini-batch is stored in a buffer and
iterated upon multiple times. In addition to that, previously stored
experiments are also replayed.

  * •

Nearest Class Mean Classifier: Replaces the last biased fully connected
classification layer by a nearest mean classifier such as in iCarl [36].

  * •

Separated Softmax [2]: Since one softmax layer results in a bias explained in
[30, 16, 47, 2, 27], this technique employs two Softmax layers one for old
classes and one for new classes. Thus training new classes will not overly
penalize the old logits.

  * •

Review trick [6]: Adds an additional fine-tuning step using a balanced subset
of the memory buffer. This trick is used in the End-to-End method used in our
benchmarks 1.

However, when the batch size is reduced to one, the Stochastic Gradient
Descent (SGD) usually employed in most of these methods becomes noisy, making
convergence challenging. This is precisely where streaming learning comes into
play.

###  2.3 Streaming Learning

Streaming learning, a field of study since 1980 [33], primarily focuses on
i.i.d data streams and utilizes online learning methods. However, due to the
Softmax bias and SGD instability for batches of size 1, regular online
learning methods are not optimal for streaming learning on non-i.i.d data
streams.

For this case, one area of streaming learning considers the use of streaming
decision trees [21], where Hoeffding decision trees [17] are adapted to avoid
catastrophic forgetting. Those can also be combined into Streaming forests
[21, 46]. However, the issue with these types of methods is that they are slow
to train [11], and require extensive hyperparameter tuning, making them
unsuited for fast-paced streaming scenarios and real-time on-device learning.

Another approach involves employing a Nearest Mean Classifier [32] instead of
a Softmax layer. Research conducted by [28] has demonstrated that this simple
yet effective substitute not only addresses recency bias but also avoids
structural changes in the Fully-Connected layer when new classes are
encountered. Notably, this method has been effectively employed by iCarl [36].

Another method used is Exstream [13]. This method only updates fully connected
layers of a CNN while maintaining a prototype for each class. It also has a
policy for managing the buffer when it is full, merging the two closest
exemplars. But as we will see in section 5.5, this method suffers in terms of
computation time as it requires, in this case, 64 hours to run on our
experiment, whereas SRDA requires 12 hours.

Especially relevant to this paper is Streaming LDA [34] that was first used
for data streams and has since been adapted in [14] to work with CNNs. SLDA
uses running class means and a common covariance matrix for all classes to
assign labels to inputs based on the closest Gaussian distribution.

##  3 Problem Setting

We consider ensembles $\mathcal{X}$ and $\mathcal{Y}$, representing our
datapoints and labels, respectively. We aim to train a model $F$ with
parameters $\theta$ to accurately classify classes in $\llbracket
1,C\rrbracket$, where $C\in\mathbb{N}^{*}$. To achieve this, we adopt a
streaming fashion approach, where each datapoint $x\in\mathcal{X}$ is
individually sent to the model for fitting. Additionally, we adopt a class
incremental scenario by ordering the samples in batches of classes. We
consider this type of scenario to be the most general as it is similar to
animal and human learning scenarios.

##  4 Deep Streaming RDA

Similar to Hayes and Kanan’s work [14], our model can be formally divided into
a composition of two distinct functions $G$ and $F$, such as $y=F(G(x))$. $G$
is comprised of the initial layers of a CNN, specifically a ResNet-18 [15] in
our case, while $F$ represents our SRDA head. The early layers of a CNN, such
as those in $G$, tend to learn filters that exhibit minimal variation across
large natural image datasets and demonstrate high transferability [48].
Therefore, we made the decision to freeze the parameters of $G$ and solely
focus on training $F$.

The following subsections will present our SRDA model. We will start by
presenting discriminant analysis before presenting an initial quadratic
streaming version that led to our deep SRDA algorithm.

###  4.1 Discriminant Analysis

Discriminant analysis is a traditional machine learning algorithm that can be
used for classification [12]. It works on the hypothesis that the data follows
a Gaussian multivariate distribution that is used to calculate the log
posterior probability using Bayes’ rule.

For each training example $x\in\mathcal{X}$ and $k\in\llbracket
1,C\rrbracket$, the goal is to calculate the posterior probability in order to
classify correctly. The Bayes’ rule on the posterior probability of being in
class $k$ for an element $x$ is:

$P(y=k|\boldsymbol{x})=\frac{P(\boldsymbol{x}|y=k)P(y=k)}{P(\boldsymbol{x})}$
(1)

With $P(\boldsymbol{x}|y=k)$ modeled as a multivariate Gaussian distribution
with a mean $\mu_{k}$ and a covariance $\Sigma_{k}$:

$P(\boldsymbol{x}|y=k)=\frac{\exp{(-\frac{1}{2}(\boldsymbol{x}-\boldsymbol{\mu}_{k})^{t}\boldsymbol{\Sigma}_{k}^{-1}(\boldsymbol{x}-\boldsymbol{\mu}_{k})})}{(2\pi)^{C/2}|\boldsymbol{\Sigma}|^{1/2}}$
(2)

According to equations 1 and 2, the log of the posterior or discriminant
$\gamma_{k}$ is given as follows:

$\begin{split}\gamma_{k}=-\frac{1}{2}\log{|\boldsymbol{\Sigma}_{k}|}-\frac{1}{2}(\boldsymbol{x}-\boldsymbol{\mu}_{k})^{t}\boldsymbol{\Sigma}_{k}^{-1}(\boldsymbol{x}-\boldsymbol{\mu}_{k})\\\
+\log{P(y=k)}+B\end{split}$ (3)

Where $B\in\mathbb{R}$ is a constant.

Finally, the classification rule is written as:

$F(\boldsymbol{x})=\operatorname*{arg\,max}_{k}\gamma_{k}$ (4)

With no further assumptions, this is referred to as Quadratic Discriminant
Analysis (QDA). Linear Discriminant Analysis (LDA) and the streaming version
of it [14], constrains equation 3 and considers equal covariance matrices
between classes.

###  4.2 Streaming Discriminant Analysis

####  4.2.1 Quadratic

In order to adapt equation 3 to streams of data we need to calculate
$\mu_{k}$, $\Sigma_{k}$, and $\Sigma_{k}^{-1}$ in a streaming fashion. We
choose to replace those values by their empirical estimators.

We consider a new element $z_{t}$ and $k\in\llbracket 1,C\rrbracket$. The
update functions are written as follows, where:

  * •

$c$ is the vector of encountered classes:

$c_{(k=y,t+1)}=c_{(k=y,t)}+1$ (5)

  * •

$\hat{\mu}$ is the saved class means:

$\boldsymbol{\hat{\mu}}_{(k=y,t+1)}=\frac{c_{(k=y,t)}\boldsymbol{\hat{\mu}}_{(k=y,t)}+\boldsymbol{z}_{t}}{c_{(k=y,t)}+1}$
(6)

  * •

$\hat{\Sigma}$ is the vector containing all the class covariance matrices:

$\boldsymbol{\hat{\Sigma}}_{(k,t+1)}=\frac{t\boldsymbol{\hat{\Sigma}}_{(k,t)}+\boldsymbol{\Delta_{t}}}{t+1}$
(7)
$\boldsymbol{\Delta_{t}}=\frac{t(\boldsymbol{z}_{t}-\boldsymbol{\hat{\mu}}_{(k=y,t)})(\boldsymbol{z}_{t}-\boldsymbol{\hat{\mu}}_{(k=y,t)})^{T}}{t+1}$
(8)

  * •

$\Lambda$ is the inverse of $\Sigma$ regularized with a shrinkage coefficient
$\epsilon$:

$\boldsymbol{\Lambda}_{(k,t)}=[(1-\epsilon)\boldsymbol{\hat{\Sigma}}_{(k,t)}+\epsilon\boldsymbol{I}]^{-1}$
(9)

  * •

$P(y=k)$ is calculated by incrementally and uniformly updating it for seen
classes at time $t$. For a balanced dataset, this factor can be considered
constant but is important for unbalanced datasets serving as a corrective
term.

$P(y=k)_{t}=\frac{c_{(k=y,t)}}{\sum_{n=1}^{C}c_{(k=n,t)}}$ (10)

Applying those updates to equation 3 leads to a streaming version of QDA
mentioned by Hayes and Kanan [14]. But the problem with SQDA is that, in high
dimensionality, the number of datapoints needed to correctly empirically
estimate the covariance matrices of each class are high [10]. As we will show
in section 5, this approach struggles to translate to our high dimensional
problem and mostly works with low dimensional datasets or ones with numerous
examples per class. This prompted us to look for a regularized alternative
that solves this issue.

####  4.2.2 Regularized

Friedman [10] proposed a compromise between LDA and QDA, that shrinks the
separate covariances of QDA toward a common covariance as in LDA. Using a
coefficient $\alpha\in[0,1]$, the regularization targets the class covariance
matrices as follows:

$\boldsymbol{\bar{\Sigma}}_{(k,t)}=\alpha\boldsymbol{\hat{\Sigma}}_{(k,t)}+(1-\alpha)\boldsymbol{\hat{\Sigma}}_{t^{\prime}}$
(11)

Where $\hat{\Sigma}_{(k,t)}$ is the empirical class covariance calculated
through QDA (eq.7), and $\hat{\Sigma}_{t^{\prime}}$ the empirical covariance
matrix calculated with SLDA, in this equation 12:

$\boldsymbol{\hat{\Sigma}}_{t^{\prime}+1}=\frac{t^{\prime}\boldsymbol{\hat{\Sigma}}_{t^{\prime}}+\boldsymbol{\Delta}_{t^{\prime}}}{t^{\prime}+1}$
(12)

Replacing this new regularised $\bar{\Sigma}$ in equations 9 and 3 gives us
SRDA.

The coefficient $\alpha$ controls the degree of shrinkage of the individual
class covariance matrix estimates towards the pooled estimate. Since it is
often the case that even small amounts of regularization can largely eliminate
quite drastic instability [43], some values of $\alpha$ have the potential of
superior performance when the population class covariances substantially
differ [10]. This performance boost is clearly shown in section 5.

##  5 Experiments & Results

###  5.1 Baselines

We conducted a comprehensive analysis by comparing our method with both
streaming methods and batch streaming methods. To evaluate the performance of
our model, we utilized the metric described in [13, 19], which involves
normalizing a model’s performance by the offline model’s performance:

$\Omega_{all}=\frac{1}{T}\sum_{t=1}^{T}\frac{\rho_{t}}{\rho_{\textit{offline},t}}$
(13)

In our case, $\rho_{t}$ refers to the top-5 accuracy of our model at time $t$.

An $\Omega_{all}$ of 1 indicates that the continual learner performs equally
well as the offline model. While it is theoretically possible to achieve
results higher than one if the continual learner outperforms the offline
model, such instances are rare in practice.

Figure 2: Top-5 Accuracy on ImageNet ILSVRC-2012. We compare our SRDA with
$\alpha=0.55$ to SQDA and SLDA with a plastic (non-fixed) covariance matrix.

For comparison, we use the models and results of [14] as we follow the same
experiment settings. We don’t use models that require task labels as this is
not compatible with this more general class incremental learning.

###  5.2 Initialization

As was done in previous works [14, 6, 36], we initialize $F$ and $G$ with a
100 fixed randomly selected classes. We use the same weights for $G$ as [14]
for the first 100. The 900 remaining classes are trained incrementally with a
fixed representation for $G$ as mentioned in section 4.

###  5.3 Results

As shown in table 1, our method outperforms the streaming state-of-the-art by
5 % and is very close to the offline training of the last layer. SRDA also
outperforms iCarl, and End-to-End, which are methods that update the whole
model and can iterate multiple times on the data. It should be noted that
SQDA, as mentioned earlier, struggles in high-dimensional settings due to the
limited per-class availability of data points required for accurate estimation
of covariance matrices. To address this limitation, SRDA serves as a
corrective measure by leveraging the well-estimated LDA covariance matrix in
combination with the estimated class covariance matrices. The figure 3
provides visual evidence supporting our findings, with a grid search CV
revealing the optimal $\alpha$ value of 0.55 for this experiment. Better
results can potentially be achieved by using a more recent backbone, such as
EfficientNets [42], enabling higher accuracy with a lighter model more adapted
to on device-learning.

Table 1: $\Omega_{all}$ accuracy on ImageNet. The results marked with * are taken from [14] as our experiment follows the same conditions. Models | Streaming | CLS-IID
---|---|---
Output Layer Only: |  |
Fine-Tuning* | Yes | 0.146
ExStream* [13] | Yes | 0.569
SLDA [14] | Yes | 0.752
SQDA (ours) | Yes | 0.677
SRDA (ours) | Yes | 0.801
Representation Learning: |  |
Fine-Tuning* | Yes | 0.121
iCaRL* [36] | No | 0.692
End-to-End* [6] | No | 0.780
Offline Upper Bounds: |  |
Offline (Last Layer) | No | 0.853
Offline | No | 1.000

###  5.4 Hyperparameter tuning

Because this method requires the adjustment of a hyperparameter, alpha, one
would think that it cannot be readily used out of the box. However, in
contrast to regular machine learning hyperparameters, alpha can be modified at
the end of training with minimal additional computational costs. This is due
to the independent calculation of the two covariance matrices. Consequently,
the model can be trained using SRDA and tuned with a quick grid search CV at
the end utilizing the validation dataset without retraining. In cases where a
validation dataset is unavailable, a potential solution is to maintain a
small, class-balanced buffer specifically for hyperparameter tuning, which can
be employed at the end of training. This enables this classification technique
to be directly used and competitive with other Streaming Learning algorithms.

###  5.5 Computation

Due to its quadratic complexity, our algorithm takes 12 hours to compute,
which is considerably higher than SLDA, which takes 30 minutes on ImageNet.
Nonetheless, this is still comparatively manageable compared to other batch
learning and streaming algorithms. For example, according to [14] and our
experiences, ExStream takes 64 hours, and iCarl [36] 35 hours on the same
hardware.

Figure 3: Variations of Top-5 Accuracy on ImageNet ILSVRC-2012 with regard to
$\alpha$. An $\alpha=0$ represents a regular SLDA, whereas an $\alpha=1$
represents an SQDA.

###  5.6 Memory usage

As it is with computational consumption 5.5, SRDA consumes more memory than
SLDA as it has to store a covariance per class compared to one covariance
matrix in SLDA. For instance, in the case of ImageNet ILSVRC-2012 [39] one
needs $(1000\times 4\times(512^{2}+512))$ bytes which is equivalent to 1.051
GB. For comparison, SLDA requires 0.001 GB, ExStream requires 0.041GB, and
iCarl requires 3.011 GB.

##  6 Conclusion & Discussions

We presented Deep Streaming Regularized Discriminant Analysis, a generative
classifier able to adapt to non-iid data streams and outperform existing batch
and streaming learning algorithms when paired with a CNN. We outperformed SLDA
by 5%, iCarl by 11%, and End-to-End by 2%. This is an impressive result
considering that both iCarl and End-to-End update the whole network and should
intuitively beat a method only focusing on the last layer.

This method provides better results than SLDA at the cost of computation and
memory but remains comparatively manageable compared to other methods. SQDA is
better suited for low dimensional and low class counts problems, while SRDA
manages to adapt to high dimensional problems with the correct regularization
parameter alpha that can be found at the end of training with minimal
additional computational costs

For use cases where one would like to combine the speed of SLDA and the
performance of SRDA, one can imagine a model where SLDA is used for rapid
learning while SRDA slowly trains in the background enabling improved accuracy
in the long run.

Finally, this method represents a step forward in the research of Sustainable
AI. As presented by [7], Continual Learning is a promising candidate for
achieving Sustainable AI. This case of Streaming Learning justifies this
choice even further as it presents a more realistic application that respects
the principles of Sustainable AI, including efficiency, privacy, and
robustness. Our deep SRDA has many potential applications, including robotics,
edge learning, and human-machine interfaces. It removes the need to store the
data as the model can learn on data streams, learning at approximately 28Hz
for our experiment on ImageNet. More importantly, it enables on-device
Continual Learning, removing the need for retraining and thus saving
resources.

## Appendix

The models were trained using these parameters:

  * •

Offline: Same parameters as [14]. SGD for 90 epochs, with $lr=0.1$ with decay
at 10 30 and 60 epochs, $momentum=0.9$ and weight decay of $10^{-4}$.

  * •

iCarl: Parameters from [36], and stored 20 exemplars per class.

  * •

ExStream: Same parameters as offline with 20 exemplars per class.

## Acknowledgments

This work was performed as part of the DREAM project. The DREAM project
received funding from the European Union’s European Innovation Council (EIC)
under grant agreement No 101046451.

## References

  * [1] Wickliffe C. Abraham and Anthony Robins.  Memory retention – the synaptic stability versus plasticity dilemma.  28(2):73–78, 2005.
  * [2] Hongjoon Ahn, Jihwan Kwak, Subin Lim, Hyeonsu Bang, Hyojun Kim, and Taesup Moon.  SS-IL: Separated softmax for incremental learning.
  * [3] Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuytelaars.  Memory aware synapses: Learning what (not) to forget.
  * [4] Rahaf Aljundi, Eugene Belilovsky, Tinne Tuytelaars, Laurent Charlin, Massimo Caccia, Min Lin, and Lucas Page-Caccia.  Online continual learning with maximal interfered retrieval.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [5] Pietro Buzzega, Matteo Boschini, Angelo Porrello, Davide Abati, and Simone Calderara.  Dark experience for general continual learning: a strong, simple baseline.
  * [6] Francisco M. Castro, Manuel J. Marín-Jiménez, Nicolás Guil, Cordelia Schmid, and Karteek Alahari.  End-to-end incremental learning.  11216:241–257, 2018.  Book Title: Computer Vision – ECCV 2018 ISBN: 9783030012571 9783030012588 Place: Cham Publisher: Springer International Publishing.
  * [7] Andrea Cossu, Marta Ziosi, and Vincenzo Lomonaco.  Sustainable artificial intelligence through continual learning, 2021.
  * [8] Kudithipudi et al.  Biological underpinnings for lifelong learning machines.  4(3):196–210, 2022.
  * [9] Robert M. French.  Catastrophic forgetting in connectionist networks.  3(4):128–135, 1999.
  * [10] Jerome H. Friedman.  Regularized discriminant analysis.  84(405):165–175, 1989.
  * [11] Mohamed Medhat Gaber, Arkady Zaslavsky, and Shonali Krishnaswamy.  A survey of classification methods in data streams.  In Charu C. Aggarwal, editor, Data Streams: Models and Algorithms, Advances in Database Systems, pages 39–59. Springer US, 2007.
  * [12] Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  The Elements of Statistical Learning.  Springer Series in Statistics. Springer, 2009.
  * [13] Tyler L. Hayes, Nathan D. Cahill, and Christopher Kanan.  Memory efficient experience replay for streaming learning.
  * [14] Tyler L. Hayes and Christopher Kanan.  Lifelong machine learning with deep streaming linear discriminant analysis.  In The IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, June 2020.
  * [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.
  * [16] Saihui Hou, Xinyu Pan, Chen Change Loy, Zilei Wang, and Dahua Lin.  Learning a unified classifier incrementally via rebalancing.  pages 831–839, 2019.
  * [17] Geoff Hulten, Laurie Spencer, and Pedro Domingos.  Mining time-changing data streams.  In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’01, pages 97–106. Association for Computing Machinery, 2001.
  * [18] Ronald Kemker and Christopher Kanan.  FearNet: Brain-inspired model for incremental learning.
  * [19] Ronald Kemker, Marc McClure, Angelina Abitino, Tyler Hayes, and Christopher Kanan.  Measuring catastrophic forgetting in neural networks.  32(1), 2018.  Number: 1.
  * [20] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell.  Overcoming catastrophic forgetting in neural networks.  114(13):3521–3526, 2017.
  * [21] Łukasz Korycki and Bartosz Krawczyk.  Streaming decision trees for lifelong learning.  In Nuria Oliver, Fernando Pérez-Cruz, Stefan Kramer, Jesse Read, and Jose A. Lozano, editors, Machine Learning and Knowledge Discovery in Databases. Research Track, volume 12975, pages 502–518. Springer International Publishing, 2021.  Series Title: Lecture Notes in Computer Science.
  * [22] Cecilia S. Lee and Aaron Y. Lee.  Clinical applications of continual learning machine learning.  2(6):e279–e281, 2020.
  * [23] Sang-Woo Lee, Jin-Hwa Kim, Jaehyun Jun, Jung-Woo Ha, and Byoung-Tak Zhang.  Overcoming catastrophic forgetting by incremental moment matching.
  * [24] Jin Li, Zhong Ji, Gang Wang, Qiang Wang, and Feng Gao.  Learning from students: Online contrastive distillation network for general continual learning.  In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, pages 3215–3221. International Joint Conferences on Artificial Intelligence Organization, 2022.
  * [25] Xilai Li, Yingbo Zhou, Tianfu Wu, Richard Socher, and Caiming Xiong.  Learn to grow: A continual structure learning framework for overcoming catastrophic forgetting.  In Proceedings of the 36th International Conference on Machine Learning, pages 3925–3934. PMLR, 2019.  ISSN: 2640-3498.
  * [26] Zhizhong Li and Derek Hoiem.  Learning without forgetting.
  * [27] Zheda Mai, Ruiwen Li, Jihwan Jeong, David Quispe, Hyunwoo Kim, and Scott Sanner.  Online continual learning in image classification: An empirical survey.  469:28–51, 2022.
  * [28] Zheda Mai, Ruiwen Li, Hyunwoo Kim, and Scott Sanner.  Supervised contrastive replay: Revisiting the nearest class mean classifier in online class-incremental continual learning.  pages 3589–3599, 2021.
  * [29] Arun Mallya and Svetlana Lazebnik.  PackNet: Adding multiple tasks to a single network by iterative pruning.
  * [30] Marc Masana, Xialei Liu, Bartlomiej Twardowski, Mikel Menta, Andrew D. Bagdanov, and Joost van de Weijer.  Class-incremental learning: survey and performance evaluation on image classification.
  * [31] Michael McCloskey and Neal J. Cohen.  Catastrophic interference in connectionist networks: The sequential learning problem.  In Gordon H. Bower, editor, Psychology of Learning and Motivation, volume 24, pages 109–165. Academic Press, 1989.
  * [32] Thomas Mensink, Jakob Verbeek, Florent Perronnin, and Gabriela Csurka.  Distance-based image classification: Generalizing to new classes at near-zero cost.  35(11):2624–2637, 2013.  Conference Name: IEEE Transactions on Pattern Analysis and Machine Intelligence.
  * [33] J I Mwnro and M S Paterson.  Selection and sorting with limited storage.  1980\.
  * [34] Shaoning Pang, Seiichi Ozawa, and Nikola Kasabov.  Incremental linear discriminant analysis for classification of data streams.  35(5):905–914, 2005.
  * [35] Daniel Philps, Tillman Weyde, Artur d’Avila Garcez, and Roy Batchelor.  Continual learning augmented investment decisions.
  * [36] Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H. Lampert.  iCaRL: Incremental classifier and representation learning.
  * [37] Amanda Rios and Laurent Itti.  Closed-loop memory GAN for continual learning.
  * [38] David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy P. Lillicrap, and Greg Wayne.  Experience replay for continual learning.
  * [39] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet large scale visual recognition challenge.
  * [40] Khadija Shaheen, Muhammad Abdullah Hanif, Osman Hasan, and Muhammad Shafique.  Continual learning for real-world autonomous systems: Algorithms, challenges and frameworks.
  * [41] Hanul Shin, Jung Kwon Lee, Jaehong Kim, and Jiwon Kim.  Continual learning with deep generative replay.
  * [42] Mingxing Tan and Quoc V. Le.  EfficientNet: Rethinking model scaling for convolutional neural networks, 2020.
  * [43] D. M. Titterington, Adrian F. M. Smith, and U. E. Makov.  Statistical Analysis of Finite Mixture Distributions.  Wiley, 1985.  Google-Books-ID: hZ0QAQAAIAAJ.
  * [44] Amal Rannen Triki, Rahaf Aljundi, Mathew B. Blaschko, and Tinne Tuytelaars.  Encoder based lifelong learning.  In 2017 IEEE International Conference on Computer Vision (ICCV), pages 1329–1337, 2017.
  * [45] Gido M. van de Ven, Tinne Tuytelaars, and Andreas S. Tolias.  Three types of incremental learning.  4(12):1185–1197, 2022.  Number: 12 Publisher: Nature Publishing Group.
  * [46] Joshua T. Vogelstein.  Lifelong learning forests, 2023.  Section: Technical Reports.
  * [47] Yue Wu, Yinpeng Chen, Lijuan Wang, Yuancheng Ye, Zicheng Liu, Yandong Guo, and Yun Fu.  Large scale incremental learning.
  * [48] Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson.  How transferable are features in deep neural networks?  In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
  * [49] Friedemann Zenke, Ben Poole, and Surya Ganguli.  Continual learning through synaptic intelligence.
  * [50] Chen Zeno, Itay Golan, Elad Hoffer, and Daniel Soudry.  Task agnostic continual learning using online variational bayes.


# On Generalized Carmichael Numbers

Yongyi Chen and Tae Kyu Kim

(Date: August 27, 2024)

###### Abstract.

Given an integer $k$, define $C_{k}$ as the set of integers $n>\max(k,0)$ such
that $a^{n-k+1}\equiv a\pmod{n}$ holds for all integers $a$. We establish
various multiplicative properties of the elements in $C_{k}$ and give a
sufficient condition for the infinitude of $C_{k}$. Moreover, we prove that
there are finitely many elements in $C_{k}$ with one and two prime factors if
and only if $k>0$ and $k$ is prime. In addition, if all but two prime factors
of $n\in C_{k}$ are fixed, then there are finitely many elements in $C_{k}$,
excluding certain infinite families of $n$. We also give conjectures about the
growth rate of $C_{k}$ with numerical evidence. We explore a similar question
when both $a$ and $k$ are fixed and prove that for fixed integers $a\geq 2$
and $k$, there are infinitely many integers $n$ such that $a^{n-k}\equiv
1\pmod{n}$ if and only if $(k,a)\neq(0,2)$ by building off the work of Kiss
and Phong. Finally, we discuss the multiplicative properties of positive
integers $n$ such that Carmichael function $\lambda(n)$ divides $n-k$.

##  1\. Introduction

In 1860, Fermat proved that if $p$ is a prime number, then $p$ divides
$a^{p-1}-1$ for any integer $a$ not divisible by $p$, a result now known as
_Fermat’s little theorem_. An equivalent formulation is that whenever $p$ is a
prime number, $p$ divides $a^{p}-a$ for all integers $a$. Fermat’s little
theorem gives a test for prime numbers. For a given integer $n$, randomly pick
some integers $a_{1},a_{2},a_{3},\ldots,a_{l}$. If $a_{i}^{n}\equiv
a_{i}\pmod{n}$ is true for all $1\leq i\leq l$, then it is probable that $n$
is a prime.

The question now arose for the converse of Fermat’s theorem: if an integer $n$
is such that $a^{n}\equiv a$ (mod $n$) for all integers $a$, then is $n$
necessarily prime? A counterexample to the converse was found in 1910 by
Carmichael [Car10] who noted that $561=3\times 11\times 17$ divides
$a^{561}-a$ for all integers $a$. This was proven using a result by Korselt
[Kor99] who gave an equivalent condition for a positive integer $n$ to divide
$a^{n}-a$ for all integers $a$.

In a series of papers around 1910, Carmichael extensively studied the
composite integers with this property, which have become to be known as the
_Carmichael numbers_. In 1912, Carmichael [Car12] described an algorithm to
construct these numbers, wishfully stating that “this list might be
indefinitely extended.” This conjecture was resolved in 1994 when Alford,
Granville, and Pomerance [AGP94] proved that there are infinitely many
Carmichael numbers, inspired by a heuristic argument by Erdős.

In 1939, Chernick [Che39] proved that if $6n+1,12n+1,18n+1$ are all primes,
then $(6n+1)(12n+1)(18n+1)$ is a Carmichael number. Dickson’s conjecture
states that for a finite set of linear forms $a_{1}+b_{1}n$, $a_{2}+b_{2}n$,
…, $a_{r}+b_{r}n$ with $b_{i}\geq 1$, then there are infinitely many positive
integers $n$ for which they are all prime, unless there is a congruence
condition preventing this. A proof of Dickson’s conjecture for $r=3$ would
prove that there are infinitely many Carmichael numbers of the form
$(6n+1)(12n+1)(18n+1)$. It remains an open question whether there are
infinitely many Carmichael numbers with a given number of prime factors.

A crucial fact in Carmichael’s proof that $561$ is a Carmichael number was
Korselt’s criterion, which enables us to easily determine whether an integer
$n$ is a Carmichael number from its prime factorization.

######  Proposition 1.1 (Korselt’s criterion).

A positive integer $n$ divides $a^{n}-a$ for all numbers $a\in\mathbb{N}$ if
and only if $n$ is squarefree and $p-1$ divides $n-1$ for all primes $p$
dividing $n$.

From Korselt’s criterion, we can check that $561$ is a Carmichael number since
it is squarefree, and $3-1=2$, $11-1=10$, and $17-1=16$ divide
$561-1=560=2^{4}\times 5\times 7$.

We can restate Korselt’s criterion using the Carmichael function.

######  Definition 1.2.

The _Carmichael function_ $\lambda(n)$ is the greatest order of an element in
$(\mathbb{Z}/n\mathbb{Z})^{\times}$.

It is well-known that the Carmichael function $\lambda(n)$ can be expressed in
terms of the prime factors of $n$:

######  Proposition 1.3.

Let $n$ be a positive integer with prime factorization
$\prod_{i=1}^{r}p_{i}^{e_{i}}$. The Carmichael function has the closed form
$\lambda(n)=\operatorname{lcm}_{i=1}^{r}\left\\{\lambda\left(p_{i}^{e_{i}}\right)\right\\}$
where

$\lambda(p^{e})=\begin{cases}p^{e-1}(p-1)&\text{ if $p$ is odd or
$p^{e}=2,4$}\\\ p^{e-2}(p-1)&\text{ if $p=2$ and $e>2$}\end{cases}.$

In particular, when $n$ is squarefree,
$\lambda(n)=\operatorname{lcm}_{i=1}^{r}\\{p_{i}-1\\}$.

Thus, the following is an equivalent formulation of Korselt’s criterion:

######  Proposition 1.4.

A positive integer $n$ divides $a^{n}-a$ for all numbers $a\in\mathbb{N}$ if
and only if $n$ is squarefree and $\lambda(n)$ divides $n-1$.

In this paper, we first consider the following question:

######  Question 1.5.

Given an integer $k$, for what integers $n>\max(k,0)$ is $a^{n-k+1}\equiv
a\pmod{n}$ for all integers $a$?

######  Notation 1.6.

We denote the set of positive integers $n$ that satisfy the condition in
Question 1.5 by $C_{k}$:

$C_{k}=\\{n\in\mathbb{Z}:n>\max(k,0)\text{ and }a^{n-k+1}\equiv
a\pmod{n}\text{ for all integers }a\\}.$

Question 1.5 is a natural generalization of the question about the converse of
Fermat’s little theorem, which is obtained for $k=1$. Consequently, $C_{1}$
consists of all of the prime numbers and Carmichael numbers.

While writing up this paper, we discovered that Question 1.5 was explored in
1999 by Halbeisen and Hungerbühler [HH99]. Many of our results on this
question have been previously derived in that paper. However, since some of
the results are new and some other results have different proofs, we have
included most of our results, both old and new, with our own proofs.

In Subsection 3.3, we show that for squarefree $k>0$, $kp\in C_{k}$ for all
primes $p\equiv 1\mod\left(\frac{\lambda(k)}{\gcd(\lambda(k),k)}\right)$.
Through numerical testing, we observe elements in $C_{k}$ that are not of this
form.

######  Definition 1.7.

For squarefree $k>0$, we define the _generalized Carmichael numbers_ as

$N_{k}=C_{k}\setminus\left\\{kp:p\equiv
1\mod\left(\frac{\lambda(k)}{\gcd(\lambda(k),k)}\right)\right\\}.$

For the other values of $k$, we let $N_{k}=C_{k}$.

Note that $N_{1}$ coincides with the set of Carmichael numbers. We interpret
$N_{k}$ as a type of generalized Carmichael numbers since they do not exhibit
a nice pattern with respect to the set of primes.

Next, we consider the growth rate of the counting functions

$C_{k}(X)=\lvert C_{k}\cap(0,X]\rvert$

and

$N_{k}(X)=\lvert N_{k}\cap(0,X]\rvert.$

From graphing $N_{k}(10^{7})$ against $N_{-k}(10^{7})$ for squarefree $2\leq
k\leq 1000$ in Figure 3, we give the following conjecture:

######  Conjecture 1.8.

For all integers $k$,

$\lim_{X\to\infty}\frac{N_{-k}(X)}{N_{k}(X)}=1.$

We also observe that for the same value of $X$, $N_{k}(X)$ tends to be bigger
when $k$ is squarefree and has many prime factors. Unfortunately, we do not
give any quantitative statements on this phenomenon.

Erdős [Erd56] conjectured that the number of Carmichael numbers less than $X$
is $X^{1-o(1)}$. More precisely, from a series of assumptions, he conjectured
that $N_{1}(X)$ should be asymptotically

$X\exp\left(-\frac{\log X\log\log\log X}{\log\log X}\right).$

######  Definition 1.9.

Extending the original definition by Pomerance, Selfridge, and Wagstaff
[PSW80], we define $d_{k}(X)$ by

$N_{k}(X)=X\exp\left(-d_{k}(X)\frac{\log X\log\log\log X}{\log\log X}\right).$

Pomerance, Selfridge, and Wagstaff [PSW80] proved that $\liminf d_{1}(X)\geq
1$ and suggested that $\limsup d_{1}(X)$ might be $2$. Pomerance [Pom81,
Pom89] gave a heuristic argument suggesting that $\lim d_{1}(X)=1$. Pinch
[Pin93] describes the case for $k=1$ in more detail.

By graphing $d_{k}(10^{7})$ for squarefree $-1000\leq k\leq 1000$ in Figure 4,
we find that $d_{k}(10^{7})$ for these $k$ lie between $1$ and $2$.
Unfortunately, we were unable to draw any conclusions about the limit
$\lim_{X\to\infty}d_{k}(X)$ from our numerical tests.

Our second question comes from fixing the values of $a$ and $k$ in the
congruence condition $a^{n-k}\equiv 1\pmod{n}$. In general, fixing the value
of $a$ enables more positive integers $n$ to satisfy the congruence condition.
We ask the following question:

######  Question 1.10.

Let $a\geq 2$ and $k$ be fixed integers. Do there exist infinitely many
composite integers $n>\max(k,0)$ such that $a^{n-k}\equiv 1\pmod{n}$?

In 1970, Rotkiewicz [Rot70] asked about whether, for arbitrary fixed integers
$a\geq 2$ and $k>0$, there are infinity many positive integers $n$ such that
$a^{n-k}\equiv 1\pmod{n}$. The answer is affirmative in the case $k=1$; the
positive composite integers $n$ such that $a^{n-1}\equiv 1\pmod{n}$ are called
_pseudoprimes_ to base $a$. In 1963, Makowski [Mak63] proved that for $k>0$,
there are infinitely many composite integers $n$ such that $a^{n-k}\equiv
1\pmod{n}$ for any positive integer $a$ coprime to $n$. This result was proved
earlier by Morrow [Mor51] in the case $k=3$. In his proof, Makowski used the
fact that there are infinitely many integers $n$ of the form $n=k\cdot p$
(where $p$ is a prime) such that $a^{n-k}\equiv 1\pmod{n}$ for any integer $a$
if $\gcd(a,n)=1$. Naturally, $\gcd(a,k)=1$ for these numbers, and now the case
for $\gcd(a,k)>1$ remained open.

Rotkiewicz [Rot70, Rot84] showed that there are infinitely many positive
integers $n$ such that $a^{n-k}\equiv 1\pmod{n}$ if $k=3$ and $a$ is an
arbitrary fixed integer, or if $k=2$ and $a=2$. In 1987, Kiss and Phong [KP87]
gave a general solution for the case of $k>0$:

######  Theorem 1.11.

Let $a\geq 2$ and $k$ be fixed positive integers. Then there are infinitely
many positive integers $n$ such that $a^{n-k}\equiv 1\pmod{n}$.

Our contribution to this problem is the extension of the work of Kiss and
Phong to the case of $k\leq 0$, showing that for fixed integers $a\geq 2$ and
$k$, there are infinitely many positive integers $n$ that $a^{n-k}\equiv
1\pmod{n}$ if $(k,a)\neq(0,2)$. There are no integers $n>1$ satisfying
$a^{n-k}\equiv 1\pmod{n}$ if $(k,a)=(0,2)$.

The rest of the paper is structured as follows. Section 2 proves a
generalization of Korselt’s criterion, providing an equivalent condition for
$n$ to satisfy the congruence condition in Question 1.5. Section 3 looks at
special cases of $k$ for Question 1.5, in particular $k=0$, $k=1$, squarefree
$k>0$, and squarefree $k<0$. Section 4 heuristically explains why a majority
of the elements in $C_{k}$ share many factors with $k$. In Section 5, we prove
that there are finitely many integers in $C_{k}$ with one or two prime factors
and finitely many elements in $C_{k}$ of the form $lpq$ where $l$ is a fixed
integer and $p,q$ are primes, given certain restrictions. Section 6 gives
several conjectures on the growth rate of $C_{k}$, based on Erdős’s original
conjecture on the growth rate of the Carmichael numbers [Erd56]. Section 7
builds on the work of Kiss and Phong to prove that for fixed integers $a\geq
2$ and $k$, there are infinitely many integers $n$ such that $a^{n-k}\equiv
1\pmod{n}$ if and only if $(k,a)\neq(0,2)$. Finally, in Section 8, we state a
variant of Question 1.5 and prove some divisibility properties of the
solutions to Question 8.1 that explain why for non-squarefree $k$, there are
many integers $n$ such that $\lambda(n)$ divides $n-k$.

##  2\. Generalized Korselt’s Criterion

We prove a generalized version of Korselt’s criterion.

######  Proposition 2.1.

An integer $n>\max(k,0)$ is in $C_{k}$ if and only if $n$ is squarefree and
$\lambda(n)$ divides $n-k$.

###### Proof.

Suppose $n\in C_{k}$. By definition of the Carmichael function, there exists
an element $a\in(\mathbb{Z}/n\mathbb{Z})^{\times}$ with order $\lambda(n)$. As
$a$ is coprime to $n$, we have $a^{n-k}\equiv 1\pmod{n}$. Then, the order of
$a$ must divide the exponent on the left hand side, so $\lambda(n)\mid n-k$.
Assume for the sake of contradiction that $n$ were not squarefree, so
$p^{2}\mid n$ for some prime $p$. Then we must have $p^{n-k+1}\equiv
p\pmod{n}$, or $p^{n-k+1}\equiv p\pmod{p^{2}}$. Notice that $n-k+1\geq 2$, so
then $0\equiv p\pmod{p^{2}}$. This is a contradiction.

Conversely, it is well-known that every element in
$(\mathbb{Z}/n\mathbb{Z})^{\times}$ has order that divides $\lambda(n)$. Thus,
if $\lambda(n)\mid n-k$, then $a^{n-k}\equiv 1\pmod{n}$ holds for all $a$
coprime to $n$.

Suppose $a$ is not coprime to $n$. We can write $a=ga^{\prime}$ where
$g=\gcd(a,n)$ and $\gcd(a^{\prime},n)=1$. From the previous paragraph, it
follows that $(a^{\prime})^{n-k+1}\equiv a^{\prime}\pmod{n}$ so it suffices to
prove that $g^{n-k+1}\equiv g\pmod{n}$. Notice that we can prime factorize
$g=p_{1}p_{2}\cdots p_{s}$ and $n=p_{1}p_{2}\cdots p_{t}$ so that $p_{i}\neq
p_{j}$ for all $i\neq j$ and $s\leq t$. This is a consequence of $g\mid n$ and
$n$ being squarefree. It is clear that $g^{n-k+1}\equiv
g\pmod{p_{1}p_{2}\cdots p_{s}}$. Since $g$ is coprime to $p_{s+1}p_{s+2}\cdots
p_{t}$ and $\lambda(p_{s+1}p_{s+2}\cdots p_{t})\mid\lambda(n)\mid n-k$, we
find that $g^{n-k+1}\equiv g\pmod{p_{s+1}p_{s+2}\cdots p_{t}}$. The Chinese
Remainder Theorem implies that $g^{n-k+1}\equiv g\pmod{n}$ as desired. ∎

######  Corollary 2.2.

An integer $n>\max(k,0)$ is in $C_{k}$ if and only if $n$ is squarefree and
for all prime factors $p$ of $n$, $p-1$ divides $n-k$.

###### Proof.

This follows from the fact that $n\in C_{k}$ implies that $n$ is squarefree,
and for squarefree $n$, $\lambda(n)=\operatorname{lcm}_{p\mid n}\\{p-1\\}$. ∎

##  3\. Special cases of $k$

###  3.1. $k=0$

Halbeisen and Hungerbühler [HH99] proved that $C_{0}=\\{1,2,6,42,1806\\}$.

###  3.2. $k=1$

By Fermat’s little theorem and the definition of Carmichael numbers, $C_{1}$
consists of every prime and every Carmichael number. It has been shown that
there are infinitely many Carmichael numbers [AGP94], so $C_{1}$ contains
infinitely many composite integers.

###  3.3. Squarefree $k>0$

It turns out most numbers in $C_{k}$ for a fixed, squarefree $k>0$ follow a
simple characterization, having $n=km$ for some positive integer $m$. As $n$
must be squarefree, we require $k$ to be squarefree and $m$ to be coprime to
$k$.

Note that $\lambda(n)=\operatorname{lcm}(\lambda(k),\lambda(m))$. Thus,
satisfying the generalized Korselt’s criterion is equivalent to satisfying two
conditions:

$\lambda(k)\mid k(m-1)$ (3.1)

and

$\lambda(m)\mid k(m-1).$ (3.2)

Condition (3.1) reduces to

$\frac{\lambda(k)}{\gcd(\lambda(k),k)}\mid m-1,$

which is a modulo condition on $m$. Condition (3.2) can be better understood
by noting that if $m$ is a prime or a Carmichael number, then the condition is
satisfied because we have $\lambda(m)\mid m-1$. Then, having a factor of $k$
on the right side allows the right side to be divisible by $\lambda(m)$ more
often. This allows us to define a more general type of Carmichael numbers:

######  Definition 3.1.

The _$k$ -Carmichael numbers_ are positive, squarefree integers $m$ such that
$\lambda(m)\mid k(m-1)$.

######  Remark 3.2.

The following are some basic properties of the $k$-Carmichael numbers.

  1. (1)

The $1$-Carmichael numbers consist of all of the primes and the Carmichael
numbers.

  2. (2)

If we have $r\mid s$ for some positive integers $r$ and $s$, then all
$r$-Carmichael numbers are $s$-Carmichael numbers.

  3. (3)

Every positive, squarefree integer $n$ is a $k$-Carmichael number for some
$k>0$.

Thus, for a fixed, squarefree $k>0$, many of the positive integers $n$ such
that $a^{n-k+1}\equiv a\pmod{n}$ for all integers $a$ are given by the
following conditions:

  * •

$n=km$ for some positive, squarefree integer $m$ coprime to $k$.

  * •

$m$ satisfies the modulo condition $m\equiv
1\pmod{\frac{\lambda(k)}{\gcd(\lambda(k),k)}}$.

  * •

$m$ is a $k$-Carmichael number. An easy way to satisfy this condition is to
let $m$ be a prime number.

Dirichlet’s prime number theorem tells us that there are infinitely many
primes $m$ that satisfy the above three conditions. Thus, $\lvert
C_{k}\rvert=\infty$ for squarefree $k>0$.

###  3.4. Squarefree $k<0$

We can apply a similar technique from the case of squarefree $k>0$ to find a
sufficient condition for the infinitude of $C_{k}$ for squarefree $k<0$.

######  Proposition 3.3.

Let $k<0$ be squarefree. If $n\in C_{-1}$,
$n\equiv-1\mod\left(\frac{\lambda(\lvert k\rvert)}{\gcd(\lambda(\lvert
k\rvert),\lvert k\rvert)}\right)$, and $\gcd(n,\lvert k\rvert)=1$, then
$\lvert k\rvert n\in C_{k}$.

###### Proof.

The assumptions on $k$ and $n$ guarantee that $\lvert k\rvert n$ is
squarefree. Now we use the generalized Korselt’s criterion to show that
$\lvert k\rvert n\in C_{k}$. We have

$\lvert k\rvert n-k=\lvert k\rvert n+\lvert k\rvert=\lvert k\rvert(n+1)\equiv
0\pmod{\lambda(n)}$ (3.3)

by our assumption that $n\in C_{-1}$. Moreover, the statement

$\lvert k\rvert n-k=\lvert k\rvert(n+1)\equiv 0\pmod{\lambda(\lvert k\rvert)}$
(3.4)

is equivalent to a divisibility condition on $n+1$, namely
$n\equiv-1\mod\left(\frac{\lambda(\lvert k\rvert)}{\gcd(\lambda(\lvert
k\rvert),\lvert k\rvert)}\right)$. As $\lvert k\rvert$ and $n$ are coprime, we
have $\operatorname{lcm}(\lambda(\lvert k\rvert),\lambda(n))=\lambda(\lvert
k\rvert n)$ and so we can combine Equations (3.3), (3.4) to obtain

$\lvert k\rvert n-k\equiv 0\pmod{\lambda(\lvert k\rvert n)},$

which shows that $\lvert k\rvert n\in C_{k}$ by Proposition 2.1. ∎

In 2012, Wright [Wri12] proved that for any coprime $a,m\in\mathbb{Z}_{>0}$,
there are infinitely many Carmichael numbers congruent to $a\pmod{m}$. If a
similar result could be found for $C_{-1}$, then Proposition 3.3 would imply
that $C_{k}$ is infinite for squarefree $k<0$ by picking
$(a,m)=\left(-1,\frac{\lvert k\rvert\cdot\lambda(\lvert
k\rvert)}{\gcd(\lambda(\lvert k\rvert),\lvert k\rvert)}\right)$. Here, $m$ is
a multiple of $k$ to ensure that the guaranteed elements in $C_{-1}$ are
coprime to $k$.

##  4\. Factors of $n$ based on $k$

In the previous sections, we saw that many elements in $C_{k}$ can be
generated by multiplying $n\in C_{\pm 1}$ by $\lvert k\rvert$ under some
modulo conditions on $n$.

Even if $n$ is not an integer multiple of $k$, it turns out that $n$ often
shares factors with $k$, a pattern that is more visible with smaller factors.
Suppose we are concerned whether $n$ and $k$ share a common divisor of $f$. If
$n$ is divisible by a prime that congruent to $1\pmod{f}$, then
$f\mid\lambda(n)$. Proposition 2.1 implies that $k\equiv n\pmod{f}$. The
hypothesis that $n$ is divisible by a prime that congruent to $1\pmod{f}$ may
appear to be rare at first, but as the size of $n$ increases, the average
number of prime factors of $n$ increases as well. Then, it becomes rare for
$n$ to have no prime factors that congruent to $1\pmod{f}$. Asymptotically,
$k\equiv n\pmod{f}$ holds. In particular, when $k$ has a factor of $f$, $n$
also has a factor of $f$. This heuristic is only broken when $n$ has only
prime factors that not congruent to $1\pmod{f}$.

######  Example.

Many elements of $C_{-11}$ are congruent to $9\pmod{10}$:

$C_{-11}=\\{\ldots,28330\mathbf{9},30622\mathbf{9},31918\mathbf{9},33724\mathbf{9},35242\mathbf{9},38278\mathbf{9},\ldots\\}.$

The above heuristic is best observed for smaller factors $f$. Here, we
consider $f=2,4$ as they produce definitive restrictions on $n$.

######  Proposition 4.1.

For any $k$, let $n\in C_{k}$. If $n>2$, then $k\equiv n\pmod{2}$.

###### Proof.

Since $n\in C_{k}$ is squarefree, if $n>2$, then $n$ is divisible by some odd
prime factor. This implies that $2\mid\lambda(n)$, so by the generalized
Korselt’s criterion, $k\equiv n\pmod{2}$. ∎

######  Proposition 4.2.

Suppose that $4\mid k$. Prime factors of elements in $C_{k}$ are either $2$ or
congruent to $3\pmod{4}$.

###### Proof.

If $n$ has a prime factor that is congruent to $1\pmod{4}$, then $k\equiv
n\pmod{4}$, or simply $4\mid n$. This means that $n$ is not squarefree and
$n\notin C_{k}$. ∎

The consequence of the previous proposition is that the growth rate of $C_{k}$
is much smaller when $4\mid k$ compared to when $4\nmid k$. More precisely,
the counting function $C_{k}(X)=\lvert C_{k}\cap(0,X]|$ grows slower whenever
$k$ is a multiple of $4$.

We believe that there should be a way to quantify this heuristic argument to
compare the growth rate of $C_{k}(X)$ across different values of $k$.

##  5\. Short Products in $C_{k}$

In this section, we investigate elements in $n\in C_{k}$ that are the products
of few primes. We also show that if all but two prime factors of $n$ are
fixed, then there are finitely many such $n$, excluding certain exceptions.

###  5.1. One prime factor

Halbeisen and Hungerühler [HH99, Proposition 4.1] showed that for any $k$,
$C_{k}$ contains finitely many primes.

###  5.2. Products of two primes

Halbeisen and Hungerbühler [HH99, Proposition 4.4] determined that for any
$k$, there are finitely many elements in $C_{k}$ with exactly two prime
factors unless $k>0$ is prime. Here, we provide an alternate proof.

######  Theorem 5.1.

There are infinitely many integers in $C_{k}$ with exactly two prime factors
if and only if $k>0$ is prime. In fact,

  1. (1)

For any $k$, there are finitely many elements in $C_{k}$ with exactly two
prime factors both coprime to $k$.

  2. (2)

If $k<0$, or $k>0$ is not prime, there are finitely many integers in $C_{k}$
with exactly two prime factors, at least one of which divides $k$.

###### Proof.

First, we prove statement (1). Suppose $pq\in C_{k}$ for distinct primes $p,q$
both coprime to $k$. By the generalized Korselt’s criterion we obtain

$p-1\mid pq-k,\quad q-1\mid pq-k.$

As $p\equiv 1\pmod{p-1}$ and $q\equiv 1\pmod{q-1}$, we get

$p-1\mid q-k,\quad q-1\mid p-k.$

The condition that $p,q$ are coprime to $k$ guarantees that the right side of
each equation is nonzero. Thus, we obtain inequalities bounding the magnitude
of each side:

$\lvert p-1\rvert\leq\lvert q-k\rvert,\quad\lvert q-1\rvert\leq\lvert
p-k\rvert.$

Graphing the intersection of the above inequalities reveals that for $k>0$, we
must have $p+q\leq k+1$, thus there are finitely many integers in $C_{k}$ with
two prime factors both coprime to $k$ if $k>0$.

For $k<0$, we obtain $\lvert p-q\rvert\leq 1-k$. Without loss of generality,
let $p<q$ to get

$p\geq q+k-1.$ (5.1)

From $p-1\mid q-k$, we obtain $\alpha(p-1)=q-k$ for some integer $\alpha$. As
$p<q$ and $k\leq-1$, we must have $\alpha\geq 2$, or $2(p-1)\leq q-k$. Thus we
obtain

$q\geq 2p+k-2.$

Solving this with Equation (5.1) gives $p<q\leq 4-3k$. Thus, there are only
finitely many integers in $C_{k}$ with exactly two prime factors both coprime
to $k$.

Now we prove statement (2). For primes $p,q$, let $pq\in C_{k}$. Without loss
of generality, let $p\mid k$. Notice that there are finitely many possibles
values of $p$. By Proposition 2.1 we obtain $q-1\mid pq-k$. As $q\equiv
1\pmod{q-1}$, we have $q-1\mid p-k$. If $k<0$, or $k>0$ and $k$ is not prime,
then $p-k\neq 0$, so $\lvert q-1\rvert\leq\lvert p-k\rvert$. This bounds the
value of $q$, which completes the proof of (2).

Noting that $C_{0}$ is finite, we have proved that there are finitely many
integers in $C_{k}$ with exactly two prime factors unless $k>0$ is prime. In
Section 3, we showed that if $k>0$ is prime, then every integer in the form
$n=k\cdot m$ for a prime $m\equiv
1\pmod{\frac{\lambda(k)}{\gcd(\lambda(k),k)}}$ with $\gcd(k,m)=1$ is in
$C_{k}$. Thus, there are infinitely many integers in $C_{k}$ with exactly two
prime factors if and only if $k>0$ and $k$ is prime. ∎

###  5.3. Products of three or more primes

It is well-known that if $6n+1,12n+1,$ and $18n+1$ are primes, then
$(6n+1)(12n+1)(18n+1)$ is a Carmichael number. Given this fact, it may be
plausible to conjecture that there are infinitely many numbers in $C_{k}$
which are products of three or more primes. However, we can prove that there
are finitely many numbers in $C_{k}$ if we fix all but two of the primes
(excluding some special cases). More precisely,

######  Proposition 5.2.

For any integers $k$ and $l>0$, there are finitely many primes $p,q$ such that
$lpq\in C_{k}$, $l\neq k$, $lp\neq k$, and $lq\neq k$.

###### Proof.

As $lpq$ must be squarefree, we can assume that $l,p,q$ are pairwise coprime.
Using Proposition 2.1 gives

$p-1\mid lpq-k,\quad q-1\mid lpq-k.$

As $p\equiv 1\pmod{p-1}$ and $q\equiv 1\pmod{q-1}$, we obtain

$p-1\mid lq-k,\quad q-1\mid lp-k.$

Let $\alpha,\beta$ be integers such that

$\alpha(p-1)=lq-k,\quad\beta(q-1)=lp-k.$ (5.2)

If $\alpha=0$ or $\beta=0$, then $lq=k$ and $lp=k$, respectively, so we can
just consider $\alpha,\beta\neq 0$.

Solve for $p$ in the first equation to get $p=\frac{lq-k}{\alpha}+1$.
Substitute this into the second equation to obtain

$\displaystyle\beta(q-1)$
$\displaystyle=l\left(\frac{lq-k}{\alpha}+1\right)-k,$
$\displaystyle\alpha\beta(q-1)$ $\displaystyle=l^{2}q-lk+\alpha l-\alpha k,$
$\displaystyle q(\alpha\beta-l^{2})$ $\displaystyle=\alpha\beta-lk+\alpha
l-\alpha k.$

Suppose $\alpha\beta-l^{2}=0$. Then, $l^{2}-lk+\alpha l-\alpha
k=(l-k)(\alpha+l)=0$. We may ignore $l=k$, so we get $\alpha=-l$ and similarly
$\beta=-l$. Adding the two equations in (5.2) then gives $l(p+q-1)=k$. There
are finitely many primes satisfying this equation with $p,q\geq 2$. Thus, we
may assume $\alpha\beta-l^{2}\neq 0$.

Solving for $q$:

$\displaystyle q$ $\displaystyle=\frac{\alpha\beta-lk+\alpha l-\alpha
k}{\alpha\beta-l^{2}},$ $\displaystyle q$
$\displaystyle=1+\frac{l^{2}-lk+\alpha l-\alpha k}{\alpha\beta-l^{2}},$
$\displaystyle q$
$\displaystyle=1+\frac{\frac{l^{2}-lk}{\alpha}+l-k}{\beta-\frac{l^{2}}{\alpha}}.$

We claim that for fixed $l,k$, the final fraction has an upper bound for
parameters $\alpha,\beta\in\mathbb{Z}$ as long as $\alpha\beta\neq l^{2}$. The
magnitude of the numerator is bounded above by $\lvert l^{2}\pm lk+l\pm
k\rvert$. For the denominator, note that for $\lvert\alpha\rvert\geq 2l^{2}$,
we have $-\frac{-1}{2}\leq\frac{l^{2}}{\alpha}\leq\frac{1}{2}$. Thus, for
$\beta\geq 1$,

$\left\lvert\beta-\frac{l^{2}}{\alpha}\right\rvert=\beta-\frac{l^{2}}{\alpha}\geq
1-\frac{1}{2}=\frac{1}{2},$

and for $\beta\leq-1$,

$\left\lvert\beta-\frac{l^{2}}{\alpha}\right\rvert=-\left(\beta-\frac{l^{2}}{\alpha}\right)\geq
1-\frac{1}{2}=\frac{1}{2}.$

This proves the lower bound of the magnitude of the denominator for
$\lvert\alpha\rvert\geq 2l^{2}$.

For each $\alpha$ in the range $\lvert\alpha\rvert<2l^{2}$, the denominator is
nonzero, so we may lower bound magnitude of the denominator by a positive
constant. Thus, the fraction is bounded above, and so is $q$. By symmetry, $p$
is also bounded above. This proves that there are finitely many primes $p,q$
such that $lpq\in C_{k}$, $l\neq k$, $lp\neq k$, and $lq\neq k$. ∎

In 1993, Pinch [Pin93] gave bounds on $\alpha$ and $\beta$ for $k=1$ to
formulate an algorithm to enumerate the Carmichael numbers up to $10^{15}$.
The following bounds that we derive for $\alpha$ and $\beta$ for the other
values of $k$ can be used to modify Pinch’s algorithm for $C_{k}$.

######  Proposition 5.3.

Let $P$ denote the largest prime factor of $l$ and assume that $P<p<q$ where
$p,q$ are primes. If $lpq\in C_{k}$, $l\neq k$, $lp\neq k$, and $lq\neq k$,
then there exist integers $\alpha,\beta$ such that

$p=1+\frac{(l-k)(l+\beta)}{\alpha\beta-l^{2}},$
$q=1+\frac{(l-k)(l+\alpha)}{\alpha\beta-l^{2}}.$

If $l>k>0$, then

$0<\alpha\beta\leq l^{2}\left(\frac{P+3}{P+1}\right).$

###### Proof.

The existence of $\alpha$ and $\beta$ was shown in the proof of Proposition
5.2.

Since $\frac{q-2}{p-1}\geq 1$ and $\frac{p}{q-1}\leq 1$, we may bound $\alpha$
and $\beta$:

$\alpha=\frac{lq-k}{p-1}=l\cdot\frac{q-2}{p-1}+\frac{2l-k}{p-1}\geq
l+\frac{2l-k}{p-1},$
$\beta=\frac{lp-k}{q-1}=l\cdot\frac{p}{q-1}-\frac{k}{q-1}\leq
l-\frac{k}{q-1}.$

From the proof of Proposition 5.2, we have

$\displaystyle(\alpha\beta-l^{2})(q-1)$ $\displaystyle=(l-k)(\alpha+l)$
$\displaystyle\geq(l-k)\left(2l+\frac{2l-k}{p-1}\right)$
$\displaystyle\geq(l-k)\left(\frac{2lp-k}{p-1}\right).$

Thus, if $l>k$, then $\alpha\beta-l^{2}>0$.

In addition, we have

$P+1\leq
p-1=\frac{(l-k)(\beta+l)}{\alpha\beta-l^{2}}\leq\frac{(l-k)\left(2l-\frac{k}{q-1}\right)}{\alpha\beta-l^{2}}.$

Thus,

$\alpha\beta-l^{2}\leq\frac{(l-k)\left(2l-\frac{k}{q-1}\right)}{P+1},$

or simplified more,

$\alpha\beta\leq
l^{2}\left(\frac{P+1+(1-\frac{k}{l})\left(2-\frac{k}{l(q-1)}\right)}{P+1}\right).$

The simplest case to consider is $k>0$, in which
$(1-\frac{k}{l})\left(2-\frac{k}{l(q-1)}\right)\leq 2$. Thus, if $l>k>0$, then

$0<\alpha\beta\leq l^{2}\cdot\frac{P+3}{P+1}.$

∎

We can also prove that there are finitely many integers $n\in C_{k}$
satisfying a particular divisibility condition on their prime factors.

######  Proposition 5.4.

If $k$ has at least $3$ prime factors (counted with multiplicity), there are
finitely many primes $p,q,r$ such that $pqr\in C_{k}$, $p-1\mid q-1$, and
$p-1\mid r-1$.

###### Proof.

Let $pqr\in C_{k}$ for primes $p,q,r$ such that $p-1\mid q-1$ and $p-1\mid
r-1$. From the generalized Korselt’s criterion, we get $p-1\mid pqr-k$. As
$p\equiv q\equiv r\equiv 1\pmod{p-1}$, this simplifies to $p-1\mid k$. This
means that there are finitely many possible values for $p$. Because $p$, $pq$,
and $pr$ have no chance of being equal to $k$, Proposition 5.2 shows that for
each of those values of $p$, there are finitely many possible values of $q$
and $r$ such that $pqr\in C_{k}$. This completes the proof. ∎

##  6\. Conjectures on the Growth Rate of $C_{k}$

In this section, we state several conjectures on the growth rate of the
counting functions

$C_{k}(X)=\lvert C_{k}\cap(0,X]\rvert$

and

$N_{k}(X)=\lvert C_{k}\cap(0,X]\rvert$

where $N_{k}$ is the set of generalized Carmichael numbers from Definition
1.7.

The prime number theorem on arithmetic progressions states that for coprime
integers $a$ and $m$, the number of primes congruent to $a\pmod{m}$ less than
$X$ is asymptotically $\phi(m)^{-1}\frac{X}{\log X}$ where $\phi$ is Euler’s
totient function.

Thus, for squarefree $k>0$, the counting function $N_{k}(X)=N_{k}\cap(1,X]$ is
asymptotically

$C_{k}(X)-\phi\left(\frac{\lambda(k)}{\gcd(\lambda(k),k)}\right)^{-1}\cdot\frac{X/k}{\log(X/k)}.$

For the other values of $k$, $N_{k}(X)=C_{k}(X)$ by definition.

Figure 1 shows $N_{k}(10^{7})$ for squarefree $2\leq k\leq 1000$. Figure 2
shows $N_{-k}(10^{7})$ for squarefree $2\leq k\leq 1000$. Figure 3 shows
$N_{k}(10^{7})$ versus $N_{-k}(10^{7})$ for squarefree $2\leq k\leq 1000$;
note that the horizontal axis is $N_{k}(10^{7})$ and the vertical axis is
$N_{-k}(10^{7})$. Each data point is color-coded based on the number of prime
factors of $k$.

Figure 1. $N_{k}(10^{7})$ for squarefree $2\leq k\leq 1000$. Figure 2.
$N_{-k}(10^{7})$ for squarefree $2\leq k\leq 1000$. Figure 3. $N_{-k}(10^{7})$
vs. $N_{k}(10^{7})$ for squarefree $2\leq k\leq 1000$.

Figures 1 and 2 illustrate that for the same value of $X$, $N_{k}(X)$ and
$N_{-k}(X)$ tend to be bigger if $k$ has many prime factors.

Moreover, Figure 3 shows that $N_{k}(X)$ and $N_{-k}(X)$ seem to grow at
similar rates with respect to $X$. Our tests show that $N_{k}(X)$ and
$N_{-k}(X)$ are similar even when $k$ is non-squarefree; unfortunately, this
is hard to show because $N_{k}(X)$ is small when $k$ is non-squarefree.
Nevertheless, we conjecture (Conjecture 1.8) that for all integers $k$,

$\lim_{X\to\infty}\frac{N_{-k}(X)}{N_{k}(X)}=1.$

In Figure 4, we graph the function $d_{k}(10^{7})$ against $d_{-k}(10^{7})$
($x$-axis and $y$-axis, respectively) where $d_{k}(X)$ is the function defined
in Definition 1.9. Re-expressing $N_{k}(X)$ as $d_{k}(X)$ seems to re-scale
the data such that the points are more uniform along the regression line.
Moreover, the re-scaling seems to clarify the existence of four clusters of
data points, formed by distinguishing the number of primes factors of $k$.

Figure 4. $d_{-k}(10^{7})$ vs. $d_{k}(10^{7})$ for squarefree $2\leq k\leq
1000$.

Unfortunately, although $d_{k}(10^{7})$ is generally smaller when $k$ has many
prime factors, it is not clear what the limit $\lim_{X\to\infty}d_{k}(X)$ may
look like with respect to $k$, if it exists at all.

##  7\. For fixed base $a$

In this section, we extend the Kiss and Phong’s proof of Theorem 1.11 to prove
that for fixed integers $a\geq 2$ and $k$, there are infinitely many integers
$n$ such that $a^{n-k}\equiv 1\pmod{n}$ if and only if $(k,a)\neq(0,2)$.
First, we note that the following key lemma of Kiss and Phong [KP87]:

######  Lemma 7.1.

Let $a,k,m$ be positive integers satisfying $a>1$, $m-k>1$, and $\gcd(a,m)=1$.
If $\operatorname{ord}_{m}(a)\mid m-k$ but $\operatorname{ord}_{m}(a)<m-k$,
then there are infinitely many positive integers $n$ that satisfy
$a^{n-k}\equiv 1\pmod{n}$, unless $m-k=2$ and $a+1$ is a power of $2$, or
$m-k=6$ and $a=2$.

This lemma generalizes for all integers $k$. Moreover, the same proof holds
since the argument is purely algebraic.

######  Lemma 7.2.

Let $a,k,m$ be integers satisfying $a>1$, $m-k>1$, $m\geq 1$, and
$\gcd(a,m)=1$. If $\operatorname{ord}_{m}(a)\mid m-k$ but
$\operatorname{ord}_{m}(a)<m-k$, then there are infinitely many positive
integers $n$ that satisfy $a^{n-k}\equiv 1\pmod{n}$, unless $m-k=2$ and $a+1$
is a power of $2$, or $m-k=6$ and $a=2$.

This enables us to extend Theorem 1.11 for all integers $k$.

######  Theorem 7.3.

If $a\geq 2$ and $k$ are integers with $(k,a)\neq(0,2)$, there are infinitely
many positive integers $n$ such that $a^{n-k}\equiv 1\pmod{n}$. If
$(k,a)=(0,2)$, then there are no integers $n>1$ such that $a^{n-k}\equiv
1\pmod{n}$.

###### Proof.

Theorem 1.11 completely solves the case $k>0$. Thus, we may assume that $k\leq
0$. For each pair of values $(k,a)$, it is sufficient to find an integer $m$
such that it satisfies the conditions of Lemma 7.2. For the following values
of $k$ and $a$, letting $m=a-1$ works:

  * •

$k=0$ and $a\geq 4$

  * •

$-1\geq k\geq-4$ and $a\geq 2$

  * •

$k=-5$ and $a\geq 3$

  * •

$k\leq-6$ and $a\geq 2$

In all of these cases, $m-k>1$, and if $m-k=6$, $a>2$. Moreover,
$\operatorname{ord}_{m}(a)=1$, so $\operatorname{ord}_{m}(a)\mid m-k$ and
$\operatorname{ord}_{m}(a)<m-k$ hold automatically. Thus, we can use Lemma
7.2.

If we try to set $m=a-1$ for $(k,a)=(0,2)$, then we have $m-k=1$, which is not
allowed. If we set $m=a-1$ for $(k,a)=(0,3)$, then $m-k=2$ and $a+1=4$, which
is also not allowed. If we set $m=a-1$ for $(k,a)=(-5,2)$, then $m-k=6$ and
$a=2$, which is not allowed.

When $(k,a)=(0,3)$, we can apply Lemma 7.2 with $m=8$, since
$\operatorname{ord}_{m}(a)=2\mid 8=m-k$. When $(k,a)=(-5,2)$, we let $m=3$ so
that $\operatorname{ord}_{m}(a)=2\mid 8=m-k$.

In the case $(k,a)=(0,2)$, we obtain the congruence relation $2^{n}\equiv
1\pmod{n}$. For the sake of contradiction, suppose that $n>1$ is an integer
such that $2^{n}\equiv 1\pmod{n}$. Let $p$ be the smallest prime divisor of
$n$ so that $2^{n}\equiv 1\pmod{p}$. Hence, $\operatorname{ord}_{p}(2)\mid n$.
However, $\operatorname{ord}_{p}(2)<p$ and since $p$ was the smallest prime
divisor $n$, $\operatorname{ord}_{p}(2)=1$. That is, $p$ divides $2^{1}-1=1$,
which is impossible. ∎

##  8\. Future Work

We hope to heuristically explain our observations of Figure 4 from Section 6
and suggest reasonable guesses for the limit $\lim d_{k}(X)$. In addition, we
note that some points from the “pf=2” category seem to be in the “pf=1”
cluster, and similarly some points from the “pf=3” category seem to be in the
“pf=2” cluster.

We are unsure why this phenomenon occurs; however, it is plausible that
$d_{k}(X)$ is proportional to a function of $k$ that is generally small when
$k$ has many prime factors, but there are subtleties based on certain
divisibility conditions on the prime factors. For example, $\lambda(k)$ is
generally small when $k$ has many prime factors, but the actual size depends
on the $\operatorname{lcm}$ of $p-1$ for all prime factors $p$ of $k$.

We may be able to learn more about $C_{k}$ by answering a variant of our
original problem.

######  Question 8.1.

Given an integer $k$, for what integers $n>\max(k,0)$ is $a^{n-k+1}\equiv
a\mod{n}$ for all integers $a$ coprime to $n$?

######  Notation 8.2.

We denote the set of positive integers $n$ that satisfy the condition in
Question 8.1 by $C^{\prime}_{k}$:

$C^{\prime}_{k}=\\{n\in\mathbb{Z}:n>\max(k,0)\text{ and }a^{n-k+1}\equiv
a\pmod{n}\text{ for all integers }a\text{ coprime to $n$}\\}.$

There is a simple condition to check that an integer is in $C^{\prime}_{k}$.

######  Proposition 8.3.

An integer $n>\max(k,0)$ is in $C^{\prime}_{k}$ if and only if $\lambda(n)\mid
n-k$.

###### Proof.

The proof is similar to that of Proposition 2.1. ∎

Note that for all integers $k$, $C_{k}\subseteq C^{\prime}_{k}$. The key
difference between $C_{k}$ and $C^{\prime}_{k}$ is that the integers in
$C_{k}$ must be squarefree while the integers in $C^{\prime}_{k}$ may be non-
squarefree.

It turns out that $C_{1}=C^{\prime}_{1}$. The _composite_ integers in
$C^{\prime}_{k}$ for $k>0$ are called the _$k$ -Knödel numbers_, named after
Walter Knödel. In 1963, Makowski [Mak63] proved that for any $k\geq 2$, there
are infinitely many composite integers $n$ such that $a^{n+k-1}\equiv
a\pmod{n}$ for all integers $a$ coprime to $n$.

Figure 5. $C^{\prime}_{0}(X)$ for $1\leq X\leq 8\times 10^{5}$.

We numerically observe that $C^{\prime}_{k}$ is large for the non-squarefree
$k$, which contrasts the pattern that $C_{k}$ is small for non-squarefree $k$.
In particular, there are many elements in $C^{\prime}_{0}$. In Figure 5, we
graph the counting function $C^{\prime}_{0}(X)=\lvert
C^{\prime}_{0}\cap(0,X]\rvert$. The following two propositions may explain
this phenomenon.

First, we note that the exponents in the prime factorization of $n\in
C^{\prime}_{k}$ are bounded by $k$:

######  Proposition 8.4.

If $\lambda(n)$ divides $n-k$ and $n=\prod_{i=1}^{r}p_{i}^{e_{i}}$, then
$\prod_{i=1}^{r}p_{i}^{e_{i}-1}$ divides $k$.

Moreover, elements from $C_{k}$ can generate elements in $C_{kp}$ for prime
factors $p$ of $k$:

######  Proposition 8.5.

If $n\in C^{\prime}_{k}$ is a multiple of a prime $p$, then $np\in
C^{\prime}_{kp}$.

For $k=0$, Proposition 8.4 says that the exponents of the prime powers that
divide $n$ are unbounded. Proposition 8.5 implies that if $n\in
C^{\prime}_{0}$ is a multiple of a prime $p$, then $np\in C^{\prime}_{0}$.
Quantifying this property may explain the exact growth rate of
$C^{\prime}_{0}(X)$.

Moreover, Proposition 8.5 suggests two categorizations of elements in $n\in
C^{\prime}_{k}$: “old” elements for which there exists $d\mid\gcd(n,k)$ with
$d>1$ such that $\frac{n}{d}\in C^{\prime}_{k/d}$, and “new” elements without
any such $d$. Further analysis of these types of elements may lead to a
heuristic explanation for the largeness of $C^{\prime}_{k}(X)$ for non-
squarefree $k$.

##  9\. Acknowledgements

Special thanks to Stefan Wehmeier for suggesting the project and providing
advice on the best direction for research. We would like to thank the MIT
PRIMES program for the opportunity to perform research under the mentorship of
wonderful professors and graduate students.

## References

  * [AGP94] W. R. Alford, Andrew Granville, and Carl Pomerance.  There are infinitely many carmichael numbers.  Ann. Math., pages 703–722, 1994.
  * [Car10] R. D. Carmichael.  Note on a new number theory function.  Bull. Am. Math. Soc., 16(5):232–238, 1910.
  * [Car12] R. D. Carmichael.  On composite numbers $p$ which satisfy the fermat congruence $a^{p-1}\equiv 1\pmod{p}$.  Amer. Math. Monthly, 19(2):22–27, 1912.
  * [Che39] Jack Chernick.  On fermat’s simple theorem.  Bull. Amer. Math. Soc., 45(4):269–274, 1939.
  * [Erd56] Paul Erdős.  On pseudoprimes and carmichael numbers.  Publ. Math. Debrecen, 4(1956):201–206, 1956.
  * [HH99] L. Halbeisen and N. Hungerbühler.  On generalised carmichael numbers.  Hardy-Ramanujan J., 1999.
  * [Kor99] Alwin Korselt.  Probleme chinois.  L’interméd. Math., 6:143–143, 1899.
  * [KP87] Péter Kiss and Bui Minh Phong.  On a problem of a. rotkiewicz.  Math. Comp., pages 751–755, 1987.
  * [Mak63] A. Makowski.  Generalization of morrow’s d-numbers.  Bull. Belg. Math. Soc. Simon Stevin, 36:71, 1962/1963.
  * [Mor51] DC Morrow.  Some properties of d numbers.  Am. Math. Monthly, 58(5):329–330, 1951.
  * [Pin93] R. G. E. Pinch.  The carmichael numbers up to $10^{15}$.  Math. Comp., 61(203):381–391, 1993.
  * [Pom81] Carl Pomerance.  On the distribution of pseudoprimes.  Math. Comp., pages 587–593, 1981.
  * [Pom89] Carl Pomerance.  Two methods in elementary analytic number theory.  Number theory and applications, 265:135–161, 1989.
  * [PSW80] Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff.  The pseudoprimes to $25\cdot 10^{9}$.  Math. Comp., 35(151):1003–1026, 1980.
  * [Rot70] Andrzej Rotkiewicz.  Pseudoprime numbers and their generalizations.  University of Novi Sad, 1970.
  * [Rot84] A. Rotkiewicz.  On the congruence $2^{n-2}\equiv 1\pmod{n}$.  Math. Comp., pages 271–272, 1984.
  * [Wri12] Thomas Wright.  Infinitely many carmichael numbers in arithmetic progressions.  arXiv preprint arXiv:1212.5850, 2012.