خب شما اصلا تعریف اعداد Carmichael را اشتباه نوشتهاید.
یک: زمانی که میگوئید عدد مرکب فلان، بعد فلان بودن را مینویسید «عدد اولی که شرطی را داشته باشد»، تناقض میسازید! چگونه یک عدد مرکب میتواند یک عدد اولی باشد که حالا یک سری ویژگی را بخواهد داشته باشد یا نداشتهباشد؟
دو: رابطهٔ همنهشتیای که اشاره کردید قرار نیست برای تمام $a$ها برقرار باشد یا اینکه برای تمام $a$ها برقرار نباشد! اینجای تعریف را هم اشتباه نوشتید.
تعریف درست: یک عدد مرکبِ $n$ را Carlmichael گویند هر گاه به ازاری هر عددی که نسبت آن اول باشد (یعنی ب.م.م. آن دو ۱ شود) مانند $m$ داشتهباشیم $m^n\overset{n}{\equiv}m$.
برای لیست کردن اعداد Carlmichael میتوانید اعداد ۱، ۲، ۳، ۴، ... را به ترتیب اول چک کنید اول هستند یا مرکب، اگر اول هستند حذف کنید. اگر مرکب بودند آنگاه تجزیهٔ آنها را بنویسید، سپس چک کنید اگر توان عدد اولی در تجزیهشان بزرگتر یا مساوی ۲ است یا خیر، اگر بلی آن عدد را حذف کنید. ولی اگر در تجزیه، هیچ عاملی با توان غیر از یک ظاهر نشدهبود آنگاه یک شرط دیگر را هم چک کنید که اگر $p$ یک عامل اول دلخواه از این عدد است، آیا $p-1$ هم $n-1$ را میشمارد؟ اگر پاسخ بلی بود، یک عدد Carlmichael دارید و گر نه این عدد را هم حذف کنید.
علت این الگوریتم قضیهای است منسوب به Korselt. میتوانید در صفحهٔ انگلیسی ویکیپدیا برای Carmichael number این قضیه را ببینید. نخستین عدد Carmichael نیز ۵۶۱ است.
