$\{ 0,1,2,\dots, 999 \}$ kümesinde, modülo $1000$ içindeki mertebesi $4$ olan elemanların toplamı kaçtır?

Question

$\color{red}{\text{Problem [Lokman GÖKÇE]}}$ $\{ 0,1,2,\dots, 999 \}$ kümesinde, çarpma işlemine göre modülo $1000$ içindeki mertebesi $4$ olan elemanların toplamı kaçtır?

Comments

cevap $1000$ mi?

---

@ElifŞuleKerem , cevap $1000$ değil ama nasıl düşündüğünüzü açıklayabilirseniz dikkat edilmesi gereken-gözden kaçan bazı noktalar düzeltilebilir.

---

Mertebeden kastını galiba ben de Elif gibi anlıyorum. Bu bir toplamsal grup ve 4 katı 100 olan 2 ya da 1 katı olmayanlar nelerdir gibi, 250 ve 750. hatta grup olarak devam edersek cevap 0 da olabilir.

4. kuvveti mod 1000de 1 olan tarzı mı soru?

---

Haklısınız, burayı belirginleştirmeliyim. Toplama işlemine göre değil, çarpma işlemine göre bir elemanın mertebesinin $4$ olmasını istiyorum. Soruyu buna göre güncelliyorum.

---

Soruyu dogru anladiysam mertebesi $4$ olan elemanlar 1, 57, 193, 249, 251, 307, 443, 499, 501, 557, 693, 749, 751, 807, 943, 999 ve bunlarin toplami 8000 yapiyor.

 

$\{57, 193, 307, 443, 557, 693, 807, 943\}$ ve bunlarin toplami $4000$ yapiyor

---

Ökkeş hocam, bu sayılardan bazılarının (çarpmaya göre) mertebesi $4$ iken bazılarının $2$, bazılarının $1$ dir. Listede fazlalık olan sayılar var. Örneğin $1^1 \equiv 1 \pmod{1000}$ olduğundan $1$'in mertebesi $4$ değil, $1$ dir. Bu, listenizdeki fazlalık olan sayılardan biridir.

Answer 1

Çözüm için anahtar nokta şu olacak:
$a$ bir çözüm ise $1000-a$ da bir çözüm olacak. 

İkinci nokta ise çözüm sayısı:
$8$ adet çözüm varlığı bize cevabın $4000$ olması gerektiğini verecek. 
Burada ek olarak 500 çözüm olur mu sorunsalı olabilirdi ama hem olmadığı bariz, hem de bu durumda tek sayıda çözüm olurdu vs vs.

Asal kuvvetlerde neye denk gelir:
Temel olarak incelememiz gereken $x^2\equiv -1\mod 125$ ve $x^4\equiv 1 \mod 8$. 

Çözüm sayısı:
İlki için $\mod 5$ gereği $2$ çözüm var. (Bu sayıları bulmak için algoritma da var, ismini unuttum.)
Diğeri için ise (ister elle, ister phi fonksiyonu ile) $4$ çözüm var. (Zaten bunlar 1,3,5,7.)
Bu ikisini Çin kalan ile birleştirirsek $8$ çözüm var. (Çin kalan ile bu 8 sayıyı bulmak da mümkün oluyor.)

Answer 2

$\color{red}{\text{Çözüm 2:}}$ Bir $x$ tam sayısının modülo $1000$ de çarpma işlemine göre mertebesi $4$ ise, $x^n \equiv 1 \pmod{1000}$ denkliğini sağlayan en küçük pozitif tam sayı $4$ olmalıdır. Yani, $x^4 \equiv 1 \pmod{1000}$ fakat $x^2 \not\equiv 1 \pmod{1000}$ olan $x$ tam sayılarını araştırıyoruz. $1000=8\cdot 125$ olduğundan $x^4 \equiv 1 \pmod{8}$ ve $x^4 \equiv 1 \pmod{125}$ olmalıdır.

 

$\color{red} {\textbf{(a)}}$ $x^4 \equiv 1 \pmod{8}$ denkliğini sağlayan değerler tek sayılar olup $1,3,5,7$ çözümleri elde edilir. Hemen şuna da dikkat edelim: bu sayılar aslında $x^2 \equiv 1 \pmod{8}$ denkliğinin de çözümleridir. Yani modülo $8$ içindeki mertebeleri $1$ veya $2$ olmaktadır. Bunu aklımızda tutarak devam edelim.

 

$\color{red} {\textbf{(b)}}$  $x^4 \equiv 1 \pmod{125}$ denkliğini çözeceğiz. (a) dan dolayı, hiçbir şekilde $x^2 \equiv 1 \pmod{125}$ denkliğini sağlayan çözümleri kabul edemeyeceğimizi biliyoruz. Aksi halde, modülo $1000$ içindeki mertebe en $1$ veya $2$ olurdu. $(x-1)(x+1)(x^2 + 1) \equiv 0 \pmod{125}$ yazalım. Bu çarpanlardan herhangi ikisi $5$ e bölünerek denkliğin sağlanması mümkün olabilir mi diye kontrol edelim.

$\color{red} \bullet$ $5\mid (x-1)$ ve $5\mid(x+1)$ mümkün değildir. Çünkü $x$, modülo $5$ de farklı kalanlar belirtir.

$\color{red} \bullet$ $5\mid (x-1)$ ve $5\mid (x^2+1)$ mümkün değildir. Çünkü $x\equiv 1 \pmod{5}$ iken $x^2 + 1 \equiv 2 \not\equiv 0 \pmod{5}$ tir.

$\color{red} \bullet$ $5\mid (x+1)$ ve $5\mid(x^2+1)$ mümkün değildir. Çünkü $x\equiv -1 \pmod{5}$ iken $x^2 + 1 \equiv 2 \not\equiv 0 \pmod{5}$ tir.

$\color{red} \bullet$ O halde çarpanlardan yalnız biri $125$ ile tam bölünmelidir. $125\mid (x-1)$ , $125\mid (x+1)$ durumlarında elde edilen sayılar sırasıyla $x\equiv 1, -1 \pmod{125}$ olup bu sayıların çarpımsal mertebesi $1$ ve $2$ dir. Dolayısıyla bu çözümleri de istemiyoruz. Geriye sadece $125\mid (x^2+1)$ durumunu incelemek kaldı. $x^2 + 1 \equiv 0 \pmod{5^3}$ denkliğinin çözüm sayısı belirlenirken ispatı Taylor polinomu kullanılarak yapılan bir türev yöntemi vardır. $x^2 + 1 \equiv 0 \pmod{5^2}$ nin çözümleri ile ilgilidir. Genelde detaylarını hatırlamadığım için, buna benzer olan aşağıdaki yöntemi tercih ediyorum.

 

Önce $x^2 + 1 \equiv 0\pmod{5}$ çözülürse $x=5k \mp 2$ formundaki çözümler elde edilir.

$\color{blue} \bullet$ $x= 5k \mp 2$ için $x^2 + 1 \equiv 0 \pmod{25}$ i çözelim. $25k^2 \mp 20k + 5 \equiv 0 \pmod{25}$ olup $5$ ile sadeleştirme yapılırsa $k\equiv \mp 1 \pmod{5}$ çözümleri bulunur. Yani $k=5t \mp 1$ olup $x = 25t + 7$ veya $x=25t - 7$ formundadır.

 $\color{blue} \bullet$ Şimdi de $x = 25t \mp 7$ sayılarını $x^2 + 1 \equiv 0 \pmod{125}$ denkliğinde yazalım. $625t^2 \mp 350t + 49 + 1 \equiv 0 \pmod{125}$ olup denkliği $25$ ile sadeleştirirsek $t\equiv \mp 2 \pmod{5}$ bulunur. $t=5n \mp 2$ değerlerini kullanarak $x=125n \mp 57$ değerlerine ulaşırız. $x$ in tek sayı olması gerektiğini de hatırlarsak $n$ çift sayı değerleri alabilir.

$x=125n + 57$ de, $n=0,2,4,6$ değerlerini alır. $x=125n-57$ de $n=2,4,6,8$ değerlerini alır. $n=2,4,6$ için $(125n + 57) + (125n -57)$ sayılarının toplamı $3000$ dir. Ayrıca $n=0$ için $57$, $n=8$ için $1000-57$ çözümlerinin toplamı da $1000$ olup genel toplam $3000 + 1000 = \boxed{4000}$ dir. (Bu değerlerin toplamını daha hızlı hesaplamak için bkz. Sercan Yılmaz'ın çözümü.)

Bu $8$ değerin tamamını görmek istersek $n$ değerlerini kullanarak $x\in \{ 57,257,557,807,193,443,693,943 \}$ buluruz.