Tübitak Lise 1. Aşama 1996 Soru 31

[matematikolimpiyati]

Aşağıdaki $a$  sayılarından hangisi için;

$n^a \equiv n \pmod a$  bağıntısını sağlamayan en az bir $n$  tam sayısı vardır?

$\textbf{a)}\ 667  \qquad\textbf{b)}\ 561  \qquad\textbf{c)}\ 547  \qquad\textbf{d)}\ 503  \qquad\textbf{e)}\ 491$

[geo]

Yanıt: $\boxed A$

Her $n \equiv 0 \pmod a$ sayısı için denkliğin sağlandığı açıktır. Bunun için $n \not \equiv 0 \pmod a$ kabul edelim.
Fermat'ın Küçük Teoremi gereği $a$ asal sayıları için $n^a \equiv n \pmod a$ daima sağlanır.
Şıklardan $a=561$ in $3$ ile bölündüğü, yani asal olmadığı hemen görülebilir.
Bu noktada şıklardaki diğer sayıların asal olup olmadığı hakkında bir test yapmadık. Ayrıca bileşik $a$ sayıları için de denklik sağlanıyor olabilir. (Nitekim böyle sayılar vardır ve bu sayılara Carmichael Sayıları denir. $561$ de ilk Carmichael Sayısıdır.)
O halde cevabın $561$ olduğunu iddia etmek yanlış bir çözüm olacaktır. (Muhtemelen $1996$ yılında bu sınava girenler arasından en yüksek puan elde eden $100$ kişi içinde hatırı sayılır sayıda ögrenci bu soruda $B$ şıkkını işaretlemiştir.)

$561= 3\cdot 11 \cdot 17$ dir.
$p \in \{3,11,17\}$ olsun.
$n \not \equiv 0 \pmod {p}$ olmak üzere;
$n^{p-1} \equiv 1 \pmod {p}$ ve $p-1 \mid 560$ olduğu için $n^{560} \equiv 1 \pmod {p}$ ve $n^{561} \equiv n \pmod {p}$ olacaktır. Diğer taraftan $n\equiv 0 \pmod p$ için zaten $n^{p} \equiv n \pmod {p}$ sağlanacaktır. Bu durumda her $n$ sayısı için $p \mid n^{561}-n$ dir.
$n^{561}-n$ sayısı hem $3$ e, hem $11$ e, hem de $17$ ye tam bölünür. Bu durumda her $n$ sayısı için $n^{561} \equiv n \pmod {561}$ dir.
O halde yanıt, $561$ olamaz.
Bu durumda şıklardaki diğer sayıların asallıklarını da test etmemiz gerekecek.

$667 = 23\cdot 29$.

$n^{667} \equiv \left (n^{22} \right )^{30}n^7 \equiv n^7 \equiv n \pmod {23}$

$2^7 \equiv 13 \not \equiv 2 \pmod {23}$

$a=667$, $n=2$ için verilen denklik sağlanmaz. Bu durumda cevap $A$ şıkkıdır.
$a=667$ için denkliği sağlamayan $n=2$ sayısını nasıl bulduk?

$23$ asal sayı olduğu için en az bir $g$ sayısı için $\operatorname{ord } _{23} (g) = 22$ dir. (Her $p$ asal sayısı için en az bir ilkel kök vardır.) Yani $g$ ilkel kökü için $g^6 \not \equiv 1 \pmod {23}$ ve $g^7 \not \equiv g \pmod {23}$. Yani $a=667$ için en az bir $n = g$ sayısı için denkliğin sağlanmadığını biliyoruz. İşin ilginç tarafı $2$, $\bmod {23}$ te bir ilkel kök değildir; ama denkliği sağlamadığı yukarıda yaptığımız gibi kolayca gösterilebilir.

$667$ in sağlamadığını gördükten sonra diğer sayıların test edilmesine gerek kalmıyor.
(Gerçekten de $491, 503, 547$ sayıları birer asal sayıdır.)

[Metin Can Aydemir]

geo hocamın da dediği gibi bu eşitliği her $n$ için sağlayan bileşik $a$ pozitif tamsayıları Carmichael sayıları olarak adlandırılır. Gerçi kullanılan tanımı şu şekildedir;

Carmichael Sayıları: Bir bileşik $a$ pozitif tamsayısı $(a,n)=1$ olan herhangi bir $n$ tamsayısı için $n^{a-1}\equiv 1\pmod{a}$ denkliğini sağlıyorsa $a$'ya Carmichael sayısı denir.

Ancak bu iki tanım denktir ve ikisi de kullanılabilir. Bununla birlikte Carmichael sayılarıyla ilgili en bilinen teorem şu şekildedir.

Teorem: Bir $n$ bileşik sayısı Carmichael sayısıdır ancak ve ancak $n$ sayısı karebölensiz ve $p\mid n$ olan her $p$ asal sayısı için $p-1\mid n-1$'dir.

Bunun ispatını yapalım. $n$ sayısının Carmichael olduğunu kabul edelim. İki tanımı da kullanabiliriz ama ben sorudaki tanımı kullanacağım. $q\mid n$ olan bir asal için $\alpha\geq 1$ için $q^{\alpha}\mid n$ olsun. Bu durumda $$q^{n-1}\equiv q\pmod{n}\implies n\mid q^{n-1}-q\implies q^{\alpha}\mid q^{n-1}-q$$ olur. $n-1>2$ olduğundan $q^{n-1}-q$ ifadesi en fazla $q$'nin birinci kuvvetine bölünür. Dolayısıyla $\alpha=1$ olmak zorundadır. Demek ki $n$'yi bölen herhangi bir asalın karesi $n$'yi bölmüyor. Bu da $n$ karebölensizdir demektir. Şimdi ise rastgele bir $p\mid n$ asalı alalım. $p$ modunda ilkel kök olan bir $m$ tamsayısını seçersek $m^d\equiv 1\pmod{p}$ olmasını sağlayan her $d$ için $p-1\mid d$ olacaktır. Mertebe konusu ile ilgili Lokman hocanın yayınladığı dersler bulunuyor, inceleyebilirsiniz. $$m^n\equiv m\pmod{n}\implies m^{n}\equiv m\pmod{p}\implies m^{n-1}\equiv 1\pmod{p}\implies p-1\mid n-1$$ bulunur.

Şimdi ise $n$'nin karebölensiz ve $p\mid n$ olan her asal sayı için $p-1\mid n-1$ olduğunu varsayalım. $n=p_1p_2\cdots p_k$ diyelim. Herhangi bir $a$ tamsayısı için $(a,n)\mid n=p_1p_2\cdots p_k$ olduğunu kenara yazalım. Çin kalan teoreminden $$a^n\equiv a\pmod{n}\iff (\text{Her  }p_i\mid n\text{  asalı için  } a^n\equiv a\pmod{p_i})$$ olur. $p_i$ asallarını $(a,n)$'yi ve dolayısıyla $a$'yı bölenler ve bölmeyenler olarak ayıralım.

Eğer $p_i\mid a$ ise $a^n\equiv a\equiv 0\pmod{p_i}$ olacağından ispatlanacak bir şey yoktur.

Eğer $p_i\not\mid a$ ise $(a,p_i)=1$'dir ve $$a^n\equiv a\pmod{p_i}\iff a^{n-1}\equiv 1\pmod{p_i}$$ olur ki bu da doğrudur çünkü $p_i-1\mid n-1$ olduğundan $$a^{n-1}\equiv \left(a^{\frac{n-1}{p_i-1}}\right)^{p_i-1}\equiv 1\pmod{p_i}$$ olur. İspat böylece biter.

Dolayısıyla ana soruya dönülecek olursa, verilen $a$ sayılarını asal çarpanlarına ayırıp, karebölensizliğine ve $p-1\mid n-1$ şartını sağlayıp sağlamadığına bakabiliriz.

$667=23\cdot 29$ için $22\not\mid 666$ olduğundan istenilen sağlanmaz ve $667$ bir Carmichael sayısı değildir.
$561=3\mid 11\mid 17$ için $2,10,16\mid 560$ olduğundan $561$ bir Carmichael saysıdır.
$547,503,491$ sayıları asal olduğundan Carmichael değildir ama Küçük Fermat teoreminden istenilen eşitliği sağlar.