540 ın mod 1003'e göre tersi nedir, nasıl bulunur

üstünde bayağı bi düşündüm ama kısa bi yol bulamadım, bulduklarımı yazayım siz seçersiniz.

1.yol
1003=17.59 olduğundan 540^(16.58)=1 (mod1003)
16.58=928 olduğundan 540^927 yi arıyoruz, bunu da karesini alarak ve 540 ile çarparak (927-926-463-462-231-230-115-114-57-56-28-14-7-6-3-2-1) yani bu sırayı 540 ın kuvvetlerinde tersten giderek buluruz.
cevap 990

2.yol
1+1003.k=540.t ifadesinde t nin tamsayı olmasını sağlayan k arıyoruz.
540=3³.4.5 olduğundan parça parça bakalım
27 modunda incelersek
1+4.k=0 olan k arıyoruz, k=20+27m şeklinde bi sayıdır
4 modunda incelersek (5 modunu da birleştirelim 1003 iki modda da 3 e denk)
1+3.k=0 , k=13+20n şeklinde bi sayıdır
bu ikisi birleşirse
zaten ikisi de 7 eksiği
20.27-7=533 olduğundan
k=533+540.s şekilli bi sayı olur
k=533 için
t=(1003.533+1)/540=990 bulunur


bu sorunun kesin kolay bir yolu vardır gibime geliyor ama şimdilik bulamadım. bi akıl tutulması yaşıyor olabilirim o yüzden uygun bi zamanda bi kez daha bakayım diyerek noktalıyorum.

ayrıca 2. yolun uzun göründüğüne bakmayın hem göründüğünden hem de 1. yoldan daha kısa

teşekürler

1003=1.540+463
540=463+77
463=6.77+1
77=77.1
yukarıdaki algoritmanın ters adımlarıyla
1=463-6.77=463-6(540-463)
=7.463-6.540=7(1003-540)-6.540
=7.1003-13.540
=> -13.540=1 (mod 1003) yani -13 yada denk olduğu 990

çözümlerden biride bu ama anlamadım özellikle algoritmanın ters adımları kısmını
anlayan varsa anlatsın lütfen

Alıntı:

---

taktik'den alıntı

1003=1.540+463
540=463+77
463=6.77+1
77=77.1

---

buradaki ilk dört satır ÖKLİD ALGORİTMASI bu algoritma iki sayının OBEB ini bulmak için kullanılır

daha sonra ters adımlarla a.1003+b.540=1 şartını sağlayan a ve b tam sayılarını buluyoruz (tabi burada 1003 ve 540 aralarında asal olduğundan bu ifade çalışr)
ters adımlarda şu şekilde işliyor:
yukardaki 3. satırdan 1 i çekip 463-6.77=1 yazılır.......(*)
2. satırdan 77 çekilip bulunan 77=540-463 ifadesi bir önceki durumda .....(*) da yazılır
463-6.(540-463)=1
463-6.540+6.463=1
7.463-6.540=1 ..........(#)
buradada 463 yerine ilk satırdan 463 çekilip bulunan 463=1003-540 ifadesi yazılırsa
7(1003-540)-6.540=1
7.1003-7.540-6.540=1
7.1003-13.540=1

demekki a.1003+b.540=1 ifadesini sağlayan a=7 ve b=-13 tam sayıları bulunur
tabi bunlar tek çözüm değildir başka a ve b tam sayılarıda vardır

bu ve daha fazlası için bence lineer diophant denklemleri hakkında internette bolca bilgi bulabilirsiniz

çok teşekür ederim ayrıntılı cevap için

Alıntı:

---

taktik'den alıntı

1003=1.540+463
540=463+77
463=6.77+1
77=77.1
yukarıdaki algoritmanın ters adımlarıyla
1=463-6.77=463-6(540-463)
=7.463-6.540=7(1003-540)-6.540
=7.1003-13.540
=> -13.540=1 (mod 1003) yani -13 yada denk olduğu 990

çözümlerden biride bu ama anlamadım özellikle algoritmanın ters adımları kısmını
anlayan varsa anlatsın lütfen

---

bu çözümü hiç düşünmemiştim ama dediğim gibi sorunun benim yaptıklarımdan pratik ya da en azından daha şık bi çözümü olmalıydı, varmış :)
hocamız da mantığını açıklamış zaten.