1640 yılında Pierre de Fermat bir arkadaşına bir mektup yazdı.

Eğer pbir asal ise ve aile bölünemeyen herhangi bir tam sayı ise p, o zaman aᵖ⁻¹ − 1ile bölünebilir p.

Arkadaşlarıma söylediğim çoğu şeyin aksine Fermat haklıydı. Fermat bunu asla kanıtlamadı. İşi, burada tüm matematik tarihinin en meşgul insanı olarak bilinen Leonhard Euler'e bıraktı. 1736'da Euler, Fermat'ın haklı olduğunu gösterdi ve iddiasını da genişletti.

Fermat'ın Küçük Teoremi

Fermat'ın kızartacak daha büyük balığı vardı, yani bu onun küçük teoremiydi. Herhangi bir asal ve asal olan ptamsayı için : olduğunu belirtir .apaᵖ⁻¹ % p = 1

Fermat neden haklıydı?

Sayı listesinin a, 2a, 3a, ..., (p-1)atümü, asal olduğu için p, ile aralarında pasaldır. Bu mod psayıların her birini kullanırsak, 1& arasındaki tüm sayıların bir listesini üretmemiz garanti edilir p-1. Çünkü p - 1belirgin sonuçlar olacaktır. Farklı olacaklarını kanıtlayabiliriz.

> if `k` & `m` are two values between `1` & `p - 1`
> to prove they are NOT distinct we would want to find
ka ≡ ma (mod p)
> because of the cancellation rule
k ≡ m (mod p)
> because `k` & `m` were defined as being less than `p`
k = m

Liste verildiğinde a, 2a, 3a, ..., (p-1)a (mod p), tam sayı kümesini elde edeceğimizi göstermiş olduk 1 -> p - 1. Bu sonuçları sıralamak bize şunu verir: 1, 2, ..., p-1.

Bir örnek işleri daha net hale getirebilir:

p = 7, a = 3
> a, 2a, 3a, ..., (p-1)a
1(3), 2(3), 3(3), 4(3), 5(3), 6(3)
3, 6, 9, 12, 15, 18
> all `mod p`
3, 6, 2, 5, 1, 4
> ordering the results
1, 2, 3, 4, 5, 6

> we know that
a, 2a, ..., (p-1)a ≡ 1, 2, ..., p-1 (mod p)
> multiplying all elements
a x 2a x ... x (p-1)a ≡ 1 x 2 x ... x (p-1) (mod p)
> simplifies
aᵖ⁻¹(p-1)! ≡ (p-1)! (mod p)
> cancel `(p-1)!`
> giving us
aᵖ⁻¹ ≡ 1 (mod p)

Euler Teoremi

Fermat'ın Küçük Teoremini kanıtlayan Euler, devam etmeye karar verdi. Herhangi iki asal tamsayı için ikisinin de asal olması gerekmediğini gösterebildi: aᵠ⁽ⁿ⁾ ≡ 1 (mod n). daha önce incelediğimiz Euler'in Totient Fonksiyonunu ifade eder . Herhangi bir tamsayının Totient işlevi, değerinden küçük eş asal sayılarını döndürür .nnn

Fermat'ın Küçük Teoreminden farklı olarak, Euler'in uzantısı, modülün asal sayı olma ihtiyacını ortadan kaldırdı. Neyse ki, bunu kanıtlamak için işin çoğunu zaten yaptık.

Fermat'ın Küçük Teoremi ile tümünün akatlarının (mod p) sayıları nasıl verdiğini hatırlayın 1 -> p-1. Bu sayı listesi , asal olduğu düşünülürse 1 -> p-1, p'nin eş asallarıydı . pBu durumda, katsayı nasal değildir, ancak , all nile çarpılan 'in eş asal sayıları listesi yine de ' 'nin eş asallarını üretir . Örneğina(mod n)n

> remembering that
(n) = Number of n's coprimes
n = 10
> n's coprimes
1, 3, 7, 9
a x 3a x 7a x 9a ≡ 1 x 3 x 7 x 9 (mod n)
> where n = 10, this gives us the number of "a" factors
aᵠ⁽¹⁰⁾
aᵠ⁽¹⁰⁾ x (1 x 3 x 7 x 9) ≡ (1 x 3 x 7 x 9) (mod n)
> cancel the coprime multiplication
aᵠ⁽¹⁰⁾ ≡ 1 (mod n)

Fermat'ın Küçük Teoremi ve Euler Teoremi, Sayılar Teorisi için çok önemlidir. Derinlemesine ele aldığımız Carmichael Fonksiyonu vakalarını çözmeye yardımcı oluyorlar . Euler'in Totient Fonksiyonunun bir örnek kullanımı olarak, izolasyonda da ilginçler.

Ve her şey yaklaşık 400 yıl önce bir arkadaşa yazılan bir mektupla başladı.

Daha ?

Dünyanın en kısa haber bültenini yazıyorum. Haftada, her Çarşamba öğrendiğim, gördüğüm veya okuduğum hızlı bir şey.

Aldığınız en erişilebilir, konuya en uygun haber bülteni olmasını istiyorum.

Denemeye değer olabilir. Abonelikten çıkmak da kolaydır.

Buna denir. Orada görüşürüz!