Tübitak Lise 1. Aşama 2021 Soru 14

[Metin Can Aydemir]

$a,b,c\in\{1,2,\dots,29\}$ olmak üzere, $$\dfrac{a^5+b^6+c^7-2021}{29}$$ ifadesinin bir tam sayı olmasını sağlayan kaç farklı $(a,b,c)$ üçlüsü vardır?

$
\textbf{a)}\ 812
\qquad\textbf{b)}\ 832
\qquad\textbf{c)}\ 836
\qquad\textbf{d)}\ 839
\qquad\textbf{e)}\ 841
$

[Metin Can Aydemir]

Cevap: $\boxed{E}$

$a^5+b^6+c^7\equiv 2021\equiv 20\pmod{29}$ olacak şekildeki $(a,b,c)$ üçlülerinin sayısı aranmaktadır. Eğer $x^5\equiv y^5\pmod{29}$ ise $x\equiv y\pmod{29}$ olduğunu gösterirsek, her farklı $a$ değeri için $a^5$ değeri $\{1,2,\dots,29\}$ kümesinin farklı bir elemanı olacağını göstermiş oluruz (birebir ve örten olacaktır da diyebiliriz), dolayısıyla her $(b,c)$ çifti için tam olarak $1$ tane $a$ değeri olmuş olur. $(b,c)$ çiftlerinin sayısı $29^2=841$ olduğundan cevap $841$  bulunur.

Şimdi $x^5\equiv y^5\pmod{29}$ ise $x\equiv y\pmod{29}$ olduğunu gösterelim. Eğer $x$ veya $y$'den en az biri $0$ ise ispatlanacak bir şey yoktur. İkisi de $0$'dan farklı ise $$\left (\dfrac{x}{y}\right )^5\equiv 1\pmod{29}$$ olacaktır. $\dfrac{x}{y}\equiv z\pmod{29}$ olacak şekilde bir $z$ vardır. Eğer $z=1$ olduğunu gösterirsek ispat biter. Yani $z^5-1\equiv 0\pmod{29}$ denkleminin tek çözümünün $z\equiv 1$ olduğunu göstermeliyiz. Bunu göstermek için ilk $14$ sayının $1$ veya $-1$ olmadığını ($1$'in kendisi haricinde) göstermemiz yeterlidir çünkü $14$'den büyük değerler için $z^5\equiv -(29-z)^5$ olacaktır. Gerçekten de hiçbir değer için sağlanmadığından $z=1$ tek çözümdür.

Dolayısıyla cevap $841$'dir.

Not: Aklıma ilk olarak $14$ sayıyı denemek geldiği için denersek çıkar yazdım ama bu biraz uzun bir yol olabilir. Eğer kısa bir çözümünü eklerseniz sevinirim.

[Squidward]

Son kısım için, $z \neq 29$ ise $z^{28} \equiv 1 \pmod{29}$ olduğundan $z$'nin periyodu $28$'in bir böleni olmalı, $z^5 \equiv 1 \pmod{29}$ da sağlanıyorsa $z$'nin periyodu $5$'in bir böleni olmalı dolayısıyla $z$'nin periyodu $(28,5) = 1$'in bir böleni olmalı bu da $z \equiv 1 \pmod{29}$ den başka çözüm olmadığını söyler şeklinde kısaltabiliriz.

[Metin Can Aydemir]

Son kısım için, $z \neq 29$ ise $z^{28} \equiv 1 \pmod{29}$ olduğundan $z$'nin periyodu $28$'in bir böleni olmalı, $z^5 \equiv 1 \pmod{29}$ da sağlanıyorsa $z$'nin periyodu $5$'in bir böleni olmalı dolayısıyla $z$'nin periyodu $(28,5) = 1$'in bir böleni olmalı bu da $z \equiv 1 \pmod{29}$ den başka çözüm olmadığını söyler şeklinde kısaltabiliriz.

Unuttuğum kısma bak yav

[DrLucky]

Çözüm için teşekkürler.

$\dfrac{x}{y}\equiv z\pmod{29}$ olacak şekilde bir $z$ vardır.

Şu kısmı neye göre söyleyebiliyoruz? Bir kesrin bir modda tam sayı karşılığı olup olmadığını nasıl anlıyoruz?

[Metin Can Aydemir]

Bezout teoreminden biliyoruz ki ikisi birden $0$ olmayan her $a$, $b$ tamsayısı için $au+bv=\text{ebob}(a,b)$ olacak şekilde $u$ ve $v$ tamsayıları vardır.

Soruda $y$'nin $0$ kalanı vermediği durumu incelediğimizi söylemiştim, yani $\text{ebob}(29,y)=1$'dir. Yani, $29u+yv=1$ olacak şekilde bir $(u,v)$ çifti bulabiliriz. $x$ ile çarparsak $x-29ux=yxv$ olur. $29\equiv 0\pmod{29}$ olduğundan ekleyip çıkartabiliriz. $$\dfrac{x}{y}\equiv \dfrac{x-29ux}{y}\equiv \dfrac{yxv}{y}\equiv xv\pmod{29}$$ olur. $xv$ tamsayı olduğundan ($xv=z$) soruda kullandığımız sonuca geliyor.

Bu, sayılar teorisinde çok kullanılan bir lemma olduğundan açıklama gereği duymamıştım ama ispatı da burada dursun, $29$ yerine $y$ ile aralarında asal herhangi bir $n$ sayısı koyabiliriz sonuç değişmez.