שינויים
/* שיטת מילר-רבין לבדיקת ראשוניות */
**<math>x^2=1</math> אם"ם <math>(x-1)(x+1)=0</math> אם"ם <math>x=\pm 1</math>
*הגדרה:
**בהנתן מספר n, ונסמן <math>n-1=2^s\cdot r</math> עבור r אי זוגי. אומרים שהמספר <math>1\leq a <n</math> הוא '''עד חזק''' לראשוניות של n אם אחד מהתנאים הבאים מתקיים:
***<math>a^r\equiv 1 \mod n</math>
***<math>a^{2^kr}\equiv -1 \mod n</math> עבור <math>1\leq k \leq s-1</math>.
*אם <math>p</math> ראשוני אזי כל המספרים <math>1<a<p</math> הם עדים חזקים לכך.**הוכחה:***לפי אוילר <math>a^{p-1}\equiv 1 \mod p</math> .***אם נעלה את <math>a^r</math> בריבוע s פעמים נקבל <math>a^{2^s\cdot r}=a^{p-1}\equiv 1 \mod p</math>.***לכן אם <math>a^r\not \equiv 1 \mod p</math>, בשלב כלשהו נעלה מספר שאינו 1 בריבוע ונקבל 1, לכן מספר זה חייב להיות <math>-1</math>.
*אם <math>p</math> אינו ראשוני, ידוע שלכל היותר רבע מבין המספרים <math>a</math> יכולים להיות עדים חזקים.
*לכן הסיכוי שמצאנו עד חזק למרות שהמספר שאנו בודקים אינו ראשוני הוא רבע.
