חבורת אוילר
חבורת אוילר היא קבוצת מספרים שלא מתחלקים ב-n. עושים בהם כפל ושומרים רק את השארית אחרי חילוק ב-n. את הקבוצה כותבים U_n. אם שני מספרים לא מתחלקים ב-n, גם המכפלה שלהם לא תתחלק ב-n. לכן הקבוצה סגורה לכפל. לכל מספר כזה יש גם מספר אחר שמכפיל אותו ומקבל 1 בשארית. המספר הזה נקרא הופכי. מספר האיברים בקבוצה...
מבחן לוקאס-להמר
מבחן לוקאס-להמר עוזר לבדוק אם מספר גדול הוא ראשוני. ראשוני פירושו שאין לו מחלקים חוץ מ-1 ומהמספר עצמו. הרעיון: בוחרים מספר קטן שנקרא עד (זה מבחן לבדיקה). מבצעים חישובים מיוחדים עם העד והמספר n. אם העד ממלא את הדרישות, אז n הוא בוודאות ראשוני. יש בעיה קטנה: צריך לדעת איך לפרק את n−1 לגורמים. פירוק ...