שינויים
/* הרצאות 6-7 הצפנה סימטרית (מפתח פרטי), הצפנה אסימטרית (מפתח ציבורי), חתימה; פרק 7 מהספר */
*אם <math>gcd(x,n)\neq 1</math>:
**כיוון ש<math>n=p\cdot q</math> אז x הוא כפולה של p או q. נוכיח במקרה שx מתחלק בp.
**קיים <math>kh<q</math> עבורו <math>x=kphp</math> וכמו כן x זר לq (אחרת בשני המקרים יוצא ש <math>x\geq n</math>).
**לכן לפי פרמה הקטן יוצא ש <math>x^{q-1}\equiv 1 \mod q</math>
**לכן <math>x^{km}=x^{k(p-1)(q-1)}=\left(x^{q-1}\right)^{k(p-1)}\equiv 1 \mod q</math>
**לכן <math>x^{de}=x^{km+1}=x^{km}x=(1+tq)x=x+tqkptqhp=x+tknth\cdot n\equiv x \mod n</math>
