İlkel Kök Uygulaması Bir Problem {Çözüldü}

[Lokman Gökçe]

Problem [Lokman Gökçe]: Ayça, Berkay, Cansu, Deniz, Emel'in her birinde 31'den az sayıda ve artan sırayla bilyeler vardır. Şöyle ilginç bir gözlemde bulunuyorlar. Beş kişinin her birinin bilye sayılarının 5. kuvvetlerinin 31 ile bölümünden kalan 5'tir. Emel'in bilyelerinin sayısı Ayça'nın bilyelerinin sayısından kaç fazladır?

(Kullanmak isteyenler için bir ek bilgi: 3, modülo 31 içinde bir ilkel köktür.)

[geo]

$x^5\equiv 5\pmod {31}$ denkliğinin $\bmod {31}$ de en fazla $5$ çözümü vardır. Soruda bizden bunların en büyüğü ile en küçüğünün farkını hesaplamamız isteniyor.

$g$ bir ilkel kök olsun.
$x$ bir çözüm ise $g^6\cdot x$ de bir çözüm olacaktır.
$x\equiv g^a$ olsun. Bu durumda tüm çözümler $k=0,1,2,3, 4$ olmak üzere $g^{6k+a} \bmod{31}$ şeklinde olacaktır.
$3$ bir ilkel kökse $3^b \equiv 5 \equiv 36 \equiv 3^2\cdot 4 \pmod{31}$ $\Longrightarrow 3^{b-2}\equiv 4 \equiv -1\cdot -4 \equiv 3^{15}\cdot 3^3 =3^{18}\pmod {31}$ $\Longrightarrow b = 20$. $x^5\equiv 3^{20}$ ise $x_1\equiv 3^4 \equiv 19 \pmod {31}$ bir çözümdür.
$3^6 \equiv 3^3\cdot 3^3 \equiv -4\cdot -4 \equiv 16 \pmod{31}$ olduğu için $x_2\equiv 19\cdot 16 \equiv 25 \pmod {31}$, $x_3 = 25\cdot 16 \equiv 28 \pmod{31}$, $x_4\equiv 28\cdot 16 \equiv 14\pmod{31}$, $x_5\equiv 14\cdot 16 \equiv 7 \pmod{31}$ olacaktır.
Aradığımız yanıt $28-7=21$ dir.

[Lokman Gökçe]

Elinize sağlık Geo hocam. Benzer bir çözümü şöyle kurgulamıştım:

$x^5 \equiv 5 \pmod{31}$ denkliğini çözmeliyiz. Modülo $31$ içinde, $3$ bir ilkel kök (primitive root) olduğundan $x \equiv 3^k \pmod{31}$ olacak şekilde $0\leq k \leq 30$ aralığında bazı $k$ tam sayıları vardır. Ayrıca $5 \equiv 3^{20} \pmod{31}$ dir. Buna göre $3^{5k} \equiv 3^{20} \pmod{31}$ yazabiliriz.

$$3^{5k - 20} \equiv 1 \pmod{31}$$

olur. İlkel kök özelliği veya çarpımsal metrebenin $30$ oluşundan dolayı $5k - 20 \equiv 0 \pmod{30}$ olup $k\equiv 4 \pmod{6}$ olur. Buradan $k\in \{ 4, 10, 16, 22, 28 \}$ değerleri elde edilir. Her bir değer için $3^k$ sayılarının modülo $31$'deki değerleri hesaplanır. Örneğin $3^{28}\equiv 7 \pmod{31}$. Bunlar sırasıyla $7, 14, 19, 25, 28$ olarak bulunur. Emel'in bilyelerinin sayısı, Ayça'nın bilyelerinin sayısından $28 - 7 = 21$ fazladır.


Not: Birkaç gün önce, yapay zeka eğitimi sürecinde ilkel kökler ile ilgili materyal hazırlamam gereken bir durum oluşmuştu. Ben de bu türde birkaç problem hazırlamıştım. Hazır konuya yoğunlaşmışken, sitemizde de bu konu ile ilgili bir soru paylaşayım istedim.

[Metin Can Aydemir]

Daha kolay olan çözümü geo hocam verdiğinden, farklı bir çözüm üretmeye çalışalım. Sayılar teorisine giriş derslerinde ilkel kök genelde sonlara doğru işlenen bir konudur, o yüzden bilmeyenler olması doğaldır. Bu konuyu bilmeyen birisi soruya nasıl yaklaşmalı minvalinde bir çözüm oluşturalım. Buradaki çözümüm karekalanlarla ilgili gözükebilir ancak iyice bakanlar sadece modüler aritmetik kullandığımızı görebilir.

$x^5\equiv 5\pmod{31}$ denkliğinin iki farklı çözümünü alalım. $x$ ve $y$ farklı ise $$x^5\equiv y^5\pmod{31}\implies x^4+x^3y+x^2y^2+xy^3+y^4\equiv 0\pmod{31}$$ elde edilir. $(y,31)=1$ olduğundan $y$'nin tersi vardır. $xy^{-1}\equiv t$ dönüşümü yaparsak, $$t^4+t^3+t^2+t+1\equiv 0\pmod{31}$$ elde edilir. $(t,31)=1$ olduğu görülebilir. $u\equiv t+t^{-1}$ dönüşümü yaparsak, $u^2-2\equiv t^2+t^{-2}$ olur. Buradan $$t^2+t+1+t^{-1}+t^{-2}\equiv u^2-2+u+1\equiv u^2+u-1\equiv 0\pmod{31}$$ bulunur. $$u^2+u-1\equiv 0\pmod{31}\iff 4u^2+4u+1\equiv 5\equiv 36\pmod{31}$$ olduğundan $$2u+1\equiv \pm 6\pmod{31}\implies 2u\equiv 5,24\pmod{31}\implies u\equiv 12,18\pmod{31}$$ bulunur. Şimdi de $t$'yi hesaplayalım. $$t+t^{-1}\equiv 18\pmod{31}\implies t^2-18t+1\equiv 0\pmod{31}\implies (t-9)^2\equiv 80\equiv 49\pmod{31}\implies t\equiv 9\pm 7\equiv 2,16\pmod{31}$$ bulunur. İkinci durumda ise $$t+t^{-1}\equiv 12\pmod{31}\implies t^2-12t+1\equiv 0\pmod{31}\implies (t-6)^2\equiv 35\equiv 4\pmod{31}\implies t\equiv 6\pm 2\equiv 4,8\pmod{31}$$ elde edilir. Yani $x^5\equiv 5\pmod{31}$ denkliğinin bir çözümü $x$ ise $2x,4x,8x,16x$ de çözüm olacaktır. Başka bir çözüm olsaydı onu da buradan bulmamız gerekirdi, dolayısıyla tüm çözümler bunlardır. Yine de $5$. dereceden olduğundan en fazla $5$ çözümü olacağını da söyleyebiliriz. Şimdi de bir çözüm bulmamız gerekiyor. $5$ çözüm olduğundan tahmini olarak $31/5= 6.2$ denemede bir çözüm bulmayı bekleyebiliriz. Bu yüzden elle deneyebiliriz. Ufak değerleri denersek, $x=7$'nin bir çözüm olduğu bulunabilir ($3$'de $-5$ bulduğumuzu fark edenler $28$'in çözüm olacağını da görecektir). Dolayısıyla, tüm çözümler, $$7,7\cdot 2,7\cdot 4,7\cdot 8,7\cdot 16\equiv 7,14,19,25,28\pmod{31}$$ olarak bulunur. $31$'den az $5$ farklı çözüm aradığımızdan Ayça'nın $7$, Emel'in ise  $28$ bilyesi olmalıdır. Aralarındaki fark ise $21$'dir.

Not: Yukarıda yaklaşık $31/5= 6.2$ denemede çözüm bulacağımızdan bahsettim ancak gerçekte $a^5\equiv -5$ bulmamız da bize $-a$'nın aradığımız çözüm olduğunu söylediğinden $31/10=3.1$ denemede çözümü buluruz. Gerçekten de $1,2,3$'ü denediğimizde $-3$'ün çözüm olduğunu bulduğumuzdan $3$ deneme yeterlidir.

[geo]

Metin Can hocam, yanlış anlamadıysam aslında çok basit bir çözüm yaptınız.

$x^5\equiv 32x^5 \equiv (2x)^5\equiv 5 \pmod {31}$ olduğu için $x$ bir çözüm ise $2x$ de bir çözüm. $2x$ bir çözüm ise  $4x$ de bir çözüm. Dolayısıyla tüm çözümler $x,2x,4x,8x,16x$ şeklinde.

[geo]

Konu ile alakalı, Elementary Number Theory, 7th Edition, David M. Burton kitabından bir teorem:

Teorem 8.12: $n$ en az bir ilkel kökü olan bir tam sayı ve $\gcd(a, n) = 1$ olsun. $d = \gcd(k, \phi(n))$ olmak üzere, $x^k \equiv a \pmod{n}$ eşitsizliğinin bir çözümünün olması için gerek ve yeter koşul $$a^{\frac{\phi(n)}{d}} \equiv 1 \pmod{n}$$ Ayrıca bir çözüm varsa, $n$ modülünde tam olarak $d$ çözüm vardır.

Kanıt: İndis alırsak, $a^{\frac{\phi(n)}{d}} \equiv 1 \pmod{n}$ denkliği, $$\frac{\phi(n)}{d} \, \text{ind} \, a \equiv 0 \pmod{\phi(n)}$$ denkliğine eşdeğerdir. Bu da, ancak ve ancak $d \mid \text{ind} \, a$ olduğunda geçerlidir. Bu, $x^k \equiv a \pmod{n}$ denkliğinin çözülebilmesi için gerek ve yeter bir koşuldur.

Doğal Sonuç: $p$ bir asal sayı ve $\gcd(a, p) = 1$ olsun. $d = \gcd(k, p - 1)$ olmak üzere; $x^k \equiv a \pmod{p}$ denkliğinin bir çözümü olması için gerek ve yeter koşul $a^{\frac{p-1}{d}} \equiv 1 \pmod{p}$ olmasıdır.

[Metin Can Aydemir]

Metin Can hocam, yanlış anlamadıysam aslında çok basit bir çözüm yaptınız.

$x^5\equiv 32x^5 \equiv (2x)^5\equiv 5 \pmod {31}$ olduğu için $x$ bir çözüm ise $2x$ de bir çözüm. $2x$ bir çözüm ise  $4x$ de bir çözüm. Dolayısıyla tüm çözümler $x,2x,4x,8x,16x$ şeklinde.

Ben ufak değerleri denemeden soruya giriştiğim için işlemlerim uzun sürdü. Daha genel bir çözüm yapmışım, bu yüzden de en başa daha zor olacak diye yazdım Gerçekten de $t^5\equiv 1\pmod{31}$'in bir çözümünü ve $x^5\equiv 5\pmod{31}$'in bir çözümünü bulursak soru bitiyor. Yukarıda da belirttiğim gibi bu çözümleri bulmak için yaklaşık üçer deneme yetiyor. $x_0$ ve $t_0$ çözümler ise (ki denediğimizde $x_0\equiv -3$ ve $t_0\equiv 2$ bulabiliyoruz) $x_0,x_0t_0,x_0t_0^2,x_0t_0^3,x_0t_0^4$'ün de tüm çözümler olduğunu görebiliriz.