Geomania.Org Forumları
Yarışma Soruları => Avrupa Kızlar Matematik Olimpiyatı => 2023 => Konuyu başlatan: matematikolimpiyati - Temmuz 02, 2023, 04:03:39 öö
-
Bir $s \geq 2$ pozitif tam sayısı verilmiştir. Her $k$ pozitif tam sayısı için, bu sayının döndürülmüşü $k'$ aşağıdaki şekilde tanımlanıyor :
$k$ sayısını $as+b$ olarak, $a,b$ negatif olmayan tam sayılar ve $b<s$ olacak şekilde yazalım, o zaman $k'=bs+a$ dır. $n$ bir pozitif tam sayı olmak üzere, $d_1=n$ ve her $i$ pozitif tam sayısı için $d_{i+1}$ sayısı $d_i$ sayısının döndürülmüşü olacak şekilde tanımlanan $d_1,d_2,...$ sonsuz dizisini alalım.
Bu dizinin $1$ sayısını içermesi için gerek ve yeter koşulun $n$ sayısının $s^2-1$ ile bölümünden kalanın ya $1$ ya da $s$ olması olduğunu gösteriniz.
-
Öncelikle $d_{k+1}$'i $d_k$ cinsinden $s^2-1$ modunda inceleyelim. $d_k=as+b$ dersek, $d_{k+1}=bs+a$ olacaktır. $s^2\equiv 1\pmod{s^2-1}$ olduğundan $$d_{k+1}\equiv bs+a \equiv bs+as^2\equiv s(as+b)\equiv sd_k\pmod{s^2-1} $$ olacaktır. $$d_{m-1}\equiv sd_m\equiv s\pmod{s^2-1}$$ $$\implies d_{m-2}\equiv sd_{m-1}\equiv s^2d_{m}\equiv d_{m}\pmod{s^2-1}$$ olacaktır. Yani $$d_{1}\equiv d_{3}\equiv \cdots\equiv d_{2k-1}\equiv n\pmod{s^2-1}$$ $$d_2\equiv d_4\equiv \cdots\equiv d_{2k}\equiv sn\pmod{s^2-1}$$ olacaktır. $d_i$'lerin hepsi ya $n$ ya da $sn$ kalanı verdiğinden dolayı $1$'i elde edebilmemiz için $n\equiv 1,s^{-1}\equiv 1,s\pmod{s^2-1}$ olmalıdır ($s$'nin tersinin yine $s$ olduğu barizdir).
Şimdi $n\equiv 1,s\pmod{s^2-1}$ olduğunu varsayalım. $k=as+b$ olarak yazımındaki $a$ ve $b$'yi $(a,b)$ olarak gösterelim. $0\leq a'<s$ için $a\equiv a'\pmod{s}$ ve $a=a'+sq$ olmak üzere $k'=bs+a=(b+q)s+a'$ olacağından $(a,b)\to (a',b')=(a',b+q)$ olur. $$a'+b'=a'+b+q=a-sq+b+q=a+b+q(1-s)\leq a+b$$ olacaktır ve eşitlik durumu sadece $q=0$ iken sağlanır (tanım gereği $q\geq 0$'dır). Yani $a+b$ toplamı artmayan bir dizidir. $q\neq 0$ oldukça $a+b$ kesin azalacağından bir noktada $q=0$ olmalıdır çünkü $a+b>0$'dır. Ayrıca bir noktada $q=0$ olursa $(a,b)\to (b,a)\to (a,b)\to \cdots$ döngüsü oluşacaktır. Bu döngünün oluşabilmesi için $a,b<s$ olmalıdır. Sonuç olarak $$as+b\leq (s-1)s+(s-1)=s^2-1$$ olacağından ve $as+b\equiv 1,s\pmod{s^2-1}$ olduğundan $as+b=1,s$ olabilir. İlk durumda istenildiği gibi $1$ sayısı $d_i$ dizisinin elemanı olur. İkinci durumda $1\cdot s+0\to 0\cdot s+1=1$ olacağından $1$ yine dizinin bir elemanı olur.
Dolayısıyla dizinin $1$ elemanını içermesi için gerek ve yeterli şart $n\equiv 1,s\pmod{s^2-1}$ olmasıdır.