🎯 تقنيات البرهان المتقدمة

إذا كان a|b، فإن b = ka حيث k عدد صحيح
إذا كان b|c، فإن c = lb حيث l عدد صحيح
إذن c = l(ka) = (lk)a، وبالتالي a|c

نفترض وجود عدد محدود من الأعداد الأولية: p₁, p₂, ..., pₙ
نعتبر العدد N = p₁ × p₂ × ... × pₙ + 1
N غير قابل للقسمة على أي من الأعداد pᵢ ← تناقض!

أساس: n=1: 1³-1 = 0، و 3|0 ✓
الاستقراء: إذا كان 3|(k³-k)، فإن 3|((k+1)³-(k+1))
(k+1)³-(k+1) = k³+3k²+3k+1-k-1 = (k³-k)+3k²+3k
= (k³-k)+3k(k+1)

الحالة 1: n ≡ 0 (mod 4) → n² ≡ 0 (mod 4)
الحالة 2: n ≡ 1 (mod 4) → n² ≡ 1 (mod 4)
الحالة 3: n ≡ 2 (mod 4) → n² ≡ 0 (mod 4)
الحالة 4: n ≡ 3 (mod 4) → n² ≡ 1 (mod 4)

(⇐) إذا كان n زوجي، فإن n = 2k، إذن n² = 4k² = 2(2k²) زوجي
(⇒) إذا كان n² زوجي و n فردي، فإن n = 2k+1
إذن n² = 4k²+4k+1 = 2(2k²+2k)+1 فردي ← تناقض

إذا كان gcd(a,b) = d، فيوجد أعداد صحيحة x,y بحيث
ax + by = d
التطبيق: إذا كان gcd(a,n) = 1، فإن a له معكوس تحت المودولو n