Öklid Algoritması

Question

$2016x+1600y=OBEB(2016,1600)$ ise $x$'in alabileceği en küçük doğal sayı değeri kaçtır?

Bunu uzun uzun yazdım ve öklid algoritmasını uyguladım.OBEB'leri 32 ve elimde en son

$32=-23.2016+29.1600$ kaldı. Buradaki $x$ değeri $-23$ olduğundan pozitife çevirmek amacıyla $1600$ ekledim ve cevabı $1577$ buldum fakat $27$ imiş cevap. :D

Comments

Konuyu bilmiyorum ama Okeklerinden yapılıyor galiba.

$OKEK(2016,1600)=OKEK(32.63,32.50)=32.63.50$

Aynı rakamsal değeri kısaca okeklerini istediğimiz gibi ekleyip çıkarırsak sonucu buluruz

$32=-23.2016+29.1600+(50.2016)-(63.1600)$

$32=27.2016-34.1600$

Answer 1

$32 = 2016x + 1600y$ ise, denklemi sadeleştirelim.

$1 = 63x + 50y$ olur. Öklid algoritmasını katsayılara uygulayalım. Ya da ben burada modüler aritmetik kullanıcam. Diğer türlü çok üşeniyorum. Hayatta uğraşamam Öklid algoritması ile.

$50y = 1-63x$ olduğuna göre

$1-63x= 0 (mod 50)$ olacaktır.

Buna göre $x = 1/13 (mod50)$ ve $1+50k = 0 (mod 13)$ olmalı.

Buna göre $k = 7 (mod 13)$ bulunur.

O halde paya $1+50.7 = 351$ eklicez. $351/13 = 27$ olup $x$ in en küçük değeri $27$ bulunur

Comments

Eline sağlık,aynı şekilde şunu farkettim

normal Öklid algoritmasını yaptıktan sonra denklemin en sade halindeki katsayıları ekleyince de yeni bulunan (x,y) sıralı ikilileri de denklemi sağlıyor.

Mesela bunu denkleştirdikten sonra

1=63x+50y oluyor,

-23+50=27 geliyor.

---

Aynen. Sağdaki katsayı kadar ekleyebiliyoruz. Çünkü,

$63.(-23) + 50.29 = 1$ olup. En genel halde çözümler

$63.(-23+50k) + 50(29-63k) = 1$ olacaktır.

Yani -23 e 50 yi eklediğin gibi, 29 dan da 63 çıkarmalısın. Çaprazlama şekilde tüm çözümler elde edilebiliyor.

---

Eyvallah yardım için teşekkürler.