Geomania.Org Forumları
Yarışma Soruları => Tübitak Kamp Sınavları => 2004 - Lise Yaz => Konuyu başlatan: matematikolimpiyati - Nisan 20, 2023, 05:31:13 ös
-
Her $a$ tam sayısı için
$$a^{\phi(n)+1} \equiv a\pmod{n}$$
koşulunu sağlayan tüm $n \geq 2$ tam sayılarını bulunuz.
-
Euler teoreminden $(a,n)=1$ için $$a^{\phi(n)}\equiv 1\pmod{n}\implies a^{\phi(n)+1}\equiv a\pmod{n}$$ olduğunu görebiliriz. Dolayısıyla sıkıntılı olacak kısım $(a,n)>1$ durumudur. $n$'nin asal çarpanlarına ayrılmış hali farklı $p_i$ asalları ve $\alpha_i\geq 1$ tamsayıları için $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ olsun. $p^{\alpha}$ kuvveti $p_i^{\alpha_i}$'lerden biri olsun. $a=p$ için $$p^{\phi(n)+1}\equiv p\pmod{n}\implies p^{\phi(n)+1}\equiv p\pmod{p^{\alpha}}\implies p^{\alpha}\mid p^{\phi(n)+1}-p$$ elde edilir. $\phi(n)\geq 1$ olduğundan $p^{\phi(n)+1}-p$'yi bölen en büyük $p$'nin kuvveti $p$'dir. Dolayısıyla $\alpha=1$ olmalıdır. Buradan da $n$'nin karekalansız olduğu sonucu çıkar. Bu durumda $n=p_1p_2\cdots p_k$ ve $\phi(n)=(p_1-1)(p_2-1)\cdots (p_k-1)$ olacaktır.
$(a,n)=q_1q_2\cdots q_m$ olsun. $q_j$'ler $p_i$'lerden bazılarıdır. Çin kalan teoreminden $$a^{\phi(n)+1}\equiv a\pmod{n}\iff n\text{'nin her } p_i \text{ asal böleni için }a^{\phi(n)+1}\equiv a\pmod{p_i}$$ Eğer $p_i$ asalı $q_j$'lerden biriyse $a\equiv 0\pmod{q_j}$ olacağından ispatlanacak bir şey yoktur. Eğer değilse, $(a,p_i)=1$'dir ve $$a^{(p_i-1)}\equiv 1\pmod{p_i}\implies a^{(p_1-1)(p_2-1)\cdots(p_k-1)}\equiv 1\pmod{p_i}\implies a^{\phi(n)+1}\equiv a\pmod{p_i}$$ elde edilir. Dolayısıyla Çin kalan teoreminden her $a$ tamsayısı ve karekalansız $n\geq 2$ için $$a^{\phi(n)+1}\equiv a\pmod{n}$$ bulunur. Şartı sağlayan tüm $n$'ler karekalansız $1$'den büyük tamsayılardır.