Matematik Olimpiyatı 2019, 2. Aşama, Soru 6

Bir \(n > 2\) tam sayısı ve bir \(a\) tam sayısı verildiğinde \(n \mid a^d - 1\) ve \(n \nmid a^{d-1} + \dots + a + 1\) şartlarını sağlayan bir \(d\) pozitif tam sayısı bulunuyorsa, \(a\) tam sayısı \(n\)-ayırandır diyelim. Bir \(n > 2\) tam sayısı verildiğinde, \(0 < a < n\) ve \(\text{obeb}(a, n) = 1\) olup \(n\)-ayıran olmayan \(a\) tam sayılarının sayısına \(n\) nın kusuru diyelim. Kusuru en küçük mümkün değere eşit olan tüm \(n > 2\) tam sayılarını bulunuz. 


**Çözüm:**

Şıklar:

Cevap:  \(n = 2^k\) (\(k \in \mathbb{Z}\) ve \(k \ge 2\)) ve \(n = 2^k \cdot 3\) (\(k \in \mathbb{Z}^+\)) formundaki sayılar

Çözüm:
\(n = 2^k\) ve \(n = 2^k \cdot 3\) için kusurun 1, diğer sayılar için 1 den çok olduğunu göstermek istiyoruz. Öncelikle \(n\)-ayıran olup olmamanın \(a'\)nın (mod \(n\))'deki değerine ait bir özellik olduğunu belirtelim. 


**Lemma 1.** \(a = -1\) sayısı \(n\)-ayıran değildir. 


\[ \text{İspat. } n \mid a^d - 1 \Rightarrow 2 \mid d \Rightarrow n \mid a^{d-1} + a^{d-2} + \dots + a + 1. \]


**Lemma 2.** \(n = 2^n \cdot s\) olsun. \(\text{obeb}(a, n) = 1\) olup da \(a \equiv -1 \pmod{2^n}\), \(\text{obeb}(a - 1, s) = 1\) ve \(2 \mid \text{mertebe}_s(a)\) olmasını sağlayan bir \(a\) sayısı \(n\)-ayıran değildir. 


İspat. \(\text{mertebe}_n(a) = \text{mertebe}_{(a-1)n}(a)\) olduğunu gösterelim. \(a \equiv -1 \pmod{4}\) varsayabiliriz. \(a-1 = 2t\) diyelim. 


\(\text{mertebe}_{(a-1)n}(a) = \text{mertebe}_{2r+1ts}(a) = \text{okek}(\text{mertebe}_{2r+1}(a), \text{mertebe}_s(a)) = \text{mertebe}_s(a)\), 


çünkü okek içindeki ilk terim 1 veya 2, ikinci terim 1'e eşit. Aynı şekilde, 


\[ \text{mertebe}_n(a) = \text{mertebe}_{2r_s}(a) = \text{okek}(\text{mertebe}_{2r}(a), \text{mertebe}_s(a)) = \text{mertebes}(a) \]


çünkü okek içindeki ilk terim 1 veyə 2'ye eşit. Bu durumda, 


\[ n \mid a^d - 1 \Rightarrow (a-1)n \mid a^d - 1 \Rightarrow n \mid a^{d-1} + a^{d-2} + ... + a + 1 = \frac{a^d - 1}{a - 1}. \]


**Lemma 3.** \(n = 2^n \cdot s\) olsun. \(s > 3\) ise, önceki lemmanın (Lemma 2) koşullarını sağlayan ve \(a \not\equiv -1 \pmod{n}\) olan \(a\) sayısı vardır. 


İspat. \(s = p^n \cdot q\), \(p\) asal, \(p \nmid q\) ve \(p^n > 3\) olsun. Çinli kalan teoreminden \(a \equiv -1 \pmod{2^n}\), \(a \equiv 2 \pmod{q}\) ve \(a\) sayısı (mod \(p^n\))'de ilkel kök olacak şekilde bir \(a\) vardır. Bu \(a\) koşulları sağlar. 


Sonuç. \(n = 2^n \cdot s\) olsun. \(s > 3 \text{ ise, } n' \text{ nin kusuru en az 2'dir. Bu Lemma 1 ve Lemma 3'ten çıkar.}\) 


**Lemma 4.** \(n = 2^n \cdot s\) ve \(s \in \{1, 3\}\) olsun. \(\text{obeb}(a, n) = 1\) ve \(a \not\equiv -1 \pmod{n}\) ise, \(a\) sayısı \(n\)-ayırandır. 


\[ \text{mertebe}_n(a) = \text{mer tebe}_{2r_s}(a) = \text{okek}(\text{merte be}_{2r}(a), \text{mertebe}_s(a)) = \text {mertebe}_{2r}(a), \]


çünkü okek içindeki ilk terim çift, ikincisi 1 veya 2'ye eşit. Ayrıca, \(2 \cdot \text{mertebe}_{2r}(a) = \text{mertebe}_{2r+1}(a) \mid \text{mertebe}_{(a-1)n}(a)\). Yani \(d = \text{mertebe}_n(a)\) için \(n \mid a^d - 1\), ancak \((a-1) \cdot n \nmid a^d - 1 \Rightarrow n \nmid a^{d-1} + a^{d-2} + ... + a +1\) olur. 


\(a \equiv 1 \pmod{2^n}\) ve \(r \ge 2\) olsun. \(s \mid a^2 - 1\) olduğundan \(n \mid a^2 - 1\) olur. Ancak \(n \nmid a + 1\). 


Geriye kalan durumda \(a \equiv -1 \pmod{2^n}\) olmalıdır. \(a \not\equiv -1 \pmod{n}\) olduğundan \(s = 3\) ve \(a \equiv 1 \pmod{3}\) olmalıdır. Yine \(n \mid a^2 - 1\) olur ancak \(3 \nmid a + 1 \Rightarrow n \nmid a + 1\) olur. 


Sonuç. \(n = 2^n \cdot s\) ve \(s \in \{1, 2\}\) olsun. \(n' \text{ nin kusuru 1'dir. Bu Lemma 1 ve Lemma 4'ten çıkar.}\)