Modüler aritmetik, Sayılar Teorisinin önemli bir alanıdır. Burada , Carmichael'in Fonksiyonunu incelerken gördüğümüz gibi , modüler aritmetik ispatları kullanan diğer matematiksel fikirleri ele alırken anlamak için yararlı olan, modüler aritmetiğin önemli ama biraz uydurma 4 yasasını ele alacağız .

notlar :

• |Sembol "kalansız bölme" anlamına gelir . x|yBaşka bir yazma biçimi de öyle y % x = 0.
• En büyük ortak bölen or GCD(x, y)verilen tüm tamsayıların kalansız bölündüğü en büyük sayıdır.
• coprime1'den büyük ortak bölenleri olmayan iki sayı birbirine göre asaldır.

• IF GCD(a, b) = 1, yani a& beş asaldır
• VE a|bc(bunun şu anlama geldiğini unutmayın bc % a = 0)
• O ZAMANLARa|c

Öklid Algoritmasını tartışırken ele aldığımız Bézout'un Kimliği'ni hatırlıyor musunuz? Herhangi bir 2 eş asal sayı için a& bdeğerlerinin aşağıdakileri karşılaması gerektiğini belirtir x:y

ax + by = 1

> multiply by `c`
acx + bcy = c
> acx divides by a
a|acx
> and because we stated that
a|bc
> so bcy must divide by a
a|bcy
> therefore divide both sides of the statement by `a`
acx/a + bcy/a = c/a

• Çünkü bunun bir tam sayı a|bcyolduğunu biliyoruz .bcy/a

Kural 2

• IF GCD(a, n) = 1(yani eş astarlar)
• VEax ≡ ay (mod n)
• O ZAMANLARx ≡ y (mod n)

> IF
ax ≡ ay (mod n)
> THEN
(ax — ay) % n = 0
> Factor out `a`
a(x-y) % n = 0
> Put differently
n|a(x-y)
> Remember that `a` & `n` are coprime
> So applying Rule 1 from above
n|(x-y)
> Meaning that
x ≡ y (mod n)

Kural 3

• IF a& neş asaldır
• SONRA öyle bir pozitif tamsayı var kkiaᵏ≡ 1 (mod n)

'nin sınırlı sayıda eş asal sayısı nvardır n. Bu değeri harfe atayalım t. Yani tkoprimerleri ndaha az olan vardır n.

Sayı listesi göz önüne alındığında:

a¹, a², ..., aᵗ, aᵗ⁺¹ (each mod n)

• Listede sadece t + 1numaralar var.
• Hepsi , ile arasında asaldır n, çünkü a, ile arasında asaldır nve yeni çarpanlar getirilmemiştir.
• Hepsi daha küçüktür n, çünkü her biri daha küçüktür mod n.

hDolayısıyla, & j, iki tamsayı olduğunu biliyoruz h < j, öyle ki:

aʰ ≡ aʲ (mod n)

> substitute out j
aʰ ≡ aʰ⁺ᵏ (mod n)
> separating exponents
aʰ ≡ aʰaᵏ (mod n)

aʰ ≡ aʰaᵏ (mod n)
> cancel aʰ
1 ≡ aᵏ (mod n)

Kural 4

• EĞERaᵏ ≡ 1 (mod n)
• VE rbir katıdırk
• aʳ≡ 1 (mod n)

Çünkü rbir katıdır, kburada bir tamsayı svardır r/k = s.

aʳ = aᵏˢ = (aᵏ)ˢ
> We know that
aᵏ ≡ 1 (mod n)
> So
aʳ ≡ (aᵏ)ˢ ≡ (1)ˢ ≡ 1 (mod n)

Az önce aşağıdakileri gösterdik:

1. a& bbirlikte asal ise, AND , a|bcSONRAa|c
2. a& bbirlikte asal ise, AND , ax ≡ ay (mod n)SONRAx ≡ y (mod n)
3. a& birlikte asal ise b, SONRA pozitif bir tamsayı vardır, köyle kiaᵏ≡ 1 (mod n)
4. aᵏ ≡ 1 (mod n)AND r, THEN'in bir kkatıysaaʳ≡ 1 (mod n)

Carmichael's Function'a baktığımızda bunların böyle bir probleme uygulandığını görebilirsiniz .

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!