Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 2000 => Konuyu başlatan: geo - Nisan 26, 2014, 05:25:20 ös
-
$f(x) = x^3 + 7x^2 + 9x + 10$ ise,
$$f(a) \equiv f(b) \pmod p \Rightarrow a\equiv b \pmod p$$ gerektirmesinin tüm $a,b$ tam sayıları için doğru olmasını $p$ nin aşağıdaki değerlerinden hangisi sağlar?
$
\textbf{a)}\ 5
\qquad\textbf{b)}\ 7
\qquad\textbf{c)}\ 11
\qquad\textbf{d)}\ 13
\qquad\textbf{e)}\ 17
$
-
Yanıt: $\boxed{C}$
Sorudaki ifadenin eşiti,
$$p | f(a) - f(b) \Rightarrow p | a -b$$ dir. İlk birkaç $f(x)$ değerlerini hesaplarsak:
$$f(0)=10, f(1)=27$$ $17|27-10$ olduğu için $E$ şıkkı elenir.
$$f(2)=64, f(3)=127$$
$5|127-27$ olduğu için $A$ şıkkı elenir.
$7|127-64$ olduğu için $B$ şıkkı elenir.
$13|127-10$ olduğu için $D$ şıkkı elenir.
Bu durumda geriye sadece $p=11$ kalır.
-
AoPS (https://artofproblemsolving.com/community/c6h490536p2750826)'te yer alan bir çözümde; $p=11$ in niçin sağladığı gösterilmiş. Burada biraz değiştirerek o çözümü tekrarlayacağım.
$a\not \equiv b \pmod {p}$ şartıyla; $a^3 + 7a^2 + 9a + 10 \equiv b^3 + 7b^2 + 9b + 10 \pmod {p}$ olsun.
Biraz düzenlemeyle; $(a^3 - b^3) + 7(a^2 - b^2) + 9(a-b) \equiv 0 \pmod {p}$ elde ederiz.
$a-b \not \equiv 0 \pmod {p}$ olduğu için denkliğin her iki tarafını $a-b$ ye bölebiliriz: $a^2 + ab + b^2 + 7a + 7b + 9 \equiv 0 \pmod {p}$.
Şimdi de denkliği $12$ ile genişletelim: $12a^2 + 12ab + 12b^2 + 84a + 84b + 108 = 3(2a+b+7)^2 + 9b^2 + 42b - 39 \equiv 0 \pmod {p}$
Şimdi denkliğin her iki tarafına $88$ ekleyelim: $3(2a+b+7)^2 + 9b^2 + 42b + 49 \equiv 3(2a+b+7)^2 + (3b+7)^2 \equiv 88 \pmod {p}$ olmalı.
$11 \mid 88$ olduğu için $p=11$ özel durumunu inceleyelim.
$m = 2a + b + 7$ ve $n=3b+7$ olsun. $3m^2 + n^2 \equiv 0 \pmod {11}$ denkliğinin çözümlerini arayalım.
$m\equiv 0 \pmod{11}$, $n\equiv 0 \pmod {11}$ bir çözümdür.
$3b+7 \equiv 0 \pmod {11}$ ve $2a+b+7 \equiv 0 \pmod {11}$ denklik sisteminin tek çözümü $a \equiv b \equiv 5 \pmod {11}$ dir. $a\not \equiv b$ olduğu için buradan çözüm gelmez.
$m \not \equiv n \pmod {11}$ olduğu durumda; $11$ asal sayı olduğu için $n \equiv km \pmod {11}$ olacak şekilde bir $k$ tam sayısı vardır.
$-3 m^2 \equiv n^2 \equiv (km)^2 \pmod {11} \Rightarrow k^2 \equiv -3 \pmod {11}$ olmalı. $-3$, $\bmod {11}$ de bir kare kalan olmadığı için buradan da çözüm gelmez.
O halde, $a\neq b$ sayıları için $f(a) \not \equiv f(b) \pmod {11}$ dir.
-
Bir önceki çözümdeki, $p=11$ için çalışan yöntemi genelleştirelim.
$a^3 + 7a^2 + 9a + 10 \equiv b^3 + 7b^2 + 9b + 10 \pmod {11}$
$\Longrightarrow (a^3 - b^3) + 7(a^2 - b^2) + 9(a-b) \equiv 0 \pmod {11}$
$\Longrightarrow a^2 + b^2 + ab + 7a + 7b + 9 \equiv 0 \pmod {11}$
$x^2 + y^2 \equiv 0 \pmod {11}$ denkliğinin çözümü yoktur. Çünkü $-1$, $\bmod {11}$ de bir kare kalan olmadığı için; $x^2 \equiv -1\cdot y^2 \pmod{11}$ denkliğini sağlayan $x$ ve $y$ yoktur.
O halde $g(a,b) = a^2 + b^2 + ab + 7a + 7b + 9 \equiv x^2 + y^2 \pmod {11}$ şeklinde yazabilirsek $a\not \equiv b$ durumunda $g(a,b) \not \equiv 0$ şartını sağlayan $a,b$ sayıları bulamamış olacağız.
$x \equiv ma + nb + r$ ve $y\equiv kb + s$ olsun.
$\begin{array}{lcl}
a^2 + b^2 + ab + 7a + 7b + 9 &\equiv & (ma + nb + r)^2 + (kb+ s)^2 \\
&\equiv & m^2a^2 + n^2b^2 + r^2 + 2mnab + 2mra + 2nrb + k^2b^2 + 2ksb + s^2 \\
&\equiv & m^2a^2 + (n^2 + k^2)b^2 + 2mnab + 2mra + (2nr +2ks)b + (r^2 + s^2)
\end{array}$
$\bmod {11}$ de; $m^2 \equiv 1$, $n^2 + k^2 \equiv 1$, $2mn \equiv 1$, $2mr \equiv 7$, $2nr+ 2ks \equiv 7$ ve $r^2 + s^2 \equiv 9$ denklik sistemini çözelim.
$m\equiv 1$ olsun.
$2mn \equiv 2n \equiv 1 \Longrightarrow n \equiv 6$.
$2mr \equiv 2r \equiv 7 \Longrightarrow r \equiv 9 \equiv -2$.
$n^2 + k^2 \equiv 36 + k^2 \equiv 1 \Longrightarrow k^2 \equiv 9 \Longrightarrow k\equiv \pm 3$
$r^2 + s^2 \equiv 9 \Longrightarrow 9^2 + s^2 \equiv 9 \Longrightarrow s^2 \equiv 5 \equiv 16 \Longrightarrow s \equiv \pm 4$.
$2nr + 2ks \equiv 2\cdot 6 \cdot 9 + 2ks \equiv 9 + 2ks \equiv 7 \Longrightarrow ks \equiv -1$. Bu durumda $k \equiv 3$, $s \equiv -4$ veya $k \equiv -3$, $s \equiv 4$ olmalı.
Gerçekten de;
$\begin{array}{lcl}
(a+6b - 2)^2 + (3b - 4)^2 &\equiv & a^2 + 36b^2 + 4 + 12ab - 4a - 24b + 9b^2 + 16 - 24b \\
&\equiv & a^2 + 45b^2 + 12ab -4a - 48b + 20 \\
&\equiv & a^2 + b^2 + ab + 7a + 7b + 9
\end{array}$