به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
0 امتیاز
25 بازدید
قبل در دانشگاه توسط tahmineh
ویرایش شده قبل توسط AmirHosein

سلام یه راهنمایی درباره نوشتن الگوریتم اعدادمرکب شبه اول( کار میکائیل) میخواستم؟؟ اعداد مرکب شبه اول یعنی همان اعداد اولی که شاهد ندارند.یعنی (a^ n همنهشت است با aبه پیمانه n به این aشاهد میگویند)

1 پاسخ

0 امتیاز
قبل توسط AmirHosein
انتخاب شده قبل توسط tahmineh
 
بهترین پاسخ

خب شما اصلا تعریف اعداد Carmichael را اشتباه نوشته‌اید. یک: زمانی که می‌گوئید عدد مرکب فلان، بعد فلان بودن را می‌نویسید «عدد اولی که شرطی را داشته باشد»، تناقض می‌سازید! چگونه یک عدد مرکب می‌تواند یک عدد اولی باشد که حالا یک سری ویژگی را بخواهد داشته باشد یا نداشته‌باشد؟ دو: رابطهٔ همنهشتی‌ای که اشاره کردید قرار نیست برای تمام $a$ها برقرار باشد یا اینکه برای تمام $a$ها برقرار نباشد! اینجای تعریف را هم اشتباه نوشتید.

تعریف درست: یک عدد مرکبِ $n$ را Carlmichael گویند هر گاه به ازاری هر عددی که نسبت آن اول باشد (یعنی ب.م.م. آن دو ۱ شود) مانند $m$ داشته‌باشیم $m^n\overset{n}{\equiv}m$.

برای لیست کردن اعداد Carlmichael می‌توانید اعداد ۱، ۲، ۳، ۴، ... را به ترتیب اول چک کنید اول هستند یا مرکب، اگر اول هستند حذف کنید. اگر مرکب بودند آنگاه تجزیهٔ آنها را بنویسید، سپس چک کنید اگر توان عدد اولی در تجزیه‌شان بزرگتر یا مساوی ۲ است یا خیر، اگر بلی آن عدد را حذف کنید. ولی اگر در تجزیه، هیچ عاملی با توان غیر از یک ظاهر نشده‌بود آنگاه یک شرط دیگر را هم چک کنید که اگر $p$ یک عامل اول دلخواه از این عدد است، آیا $p-1$ هم $n-1$ را می‌شمارد؟ اگر پاسخ بلی بود، یک عدد Carlmichael دارید و گر نه این عدد را هم حذف کنید.

علت این الگوریتم قضیه‌ای است منسوب به Korselt. می‌توانید در صفحهٔ انگلیسی ویکی‌پدیا برای Carmichael number این قضیه را ببینید. نخستین عدد Carmichael نیز ۵۶۱ است.

قبل توسط tahmineh
+1
بله، من سوالم رو اشتباه پرسیدم . خیلی ممنون اقای دکتر.
موفق باشید.

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...