aritmetik ters

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

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

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.