Tübitak Lise Takım Seçme 2011 Soru 9

[Lokman Gökçe]

$p$ bir asal sayı, $n$ bir pozitif tam sayı olsun ve $\mathbf{Z}_{p^{n}} = \{0,1,\dots, p^n -1\}$ olsun. Her $ a,b \in \mathbf{Z}_{p^{n}}$ için, ($a+b+pab$, $a+b+pab$ nin $p^n$ ye bölümünden kalanı göstermek üzere), $$f(a)+f(b)\equiv f(a+b+pab) \pmod {p^{n}}$$ koşulunu sağlayan kaç $f:\mathbf{Z}_{p^{n}}\to \mathbf{Z}_{p^{n}}$ fonksiyonunun bulunduğunu belirleyiniz.

(Okan Tekman)

[ArtOfMathSolving]

$\text{ArtOfMathSolving}$

Yanıtımız:$\boxed{p^n}$

Biraz karışık bir çözüm oldu, bu yüzden çözüm içinde gözden kaçmış hatalar bulunabilir.

$\text{Adım 1:}$ Genelliği bozmadan $a^{+}\rightarrow b^{+}$ kabul edelim ve verilen denkliği polinomsal olarak tekrar yazalım. ($\psi$ polinomun katsayılarını gösteriyor.)  $$2\sum_{i\le n} \psi_{i}a^i \equiv  \sum_{i\le n}\psi_{i}(2a+a^2p) \pmod{p^n}\Longleftrightarrow \sum_{i\le n}\psi_{i} \left( 2a^{i}-(2a+a^2p)^i\right) \equiv \sum_{i\le n}\psi_{i} (a^i+(a^i-(2a+a^2p)^i) $$ Kolaylık için $a=x,y=(2a+a^2p)$ yazalım.

$$\Rightarrow \sum_{1\le n}\psi_i(a^i-(a+a^2p))\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)\equiv 0 \pmod{p^n }\Longleftrightarrow  \sum_{1\le n}\psi_i(a^i\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)-(a^2p+a)\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right) \equiv 0 \pmod{p^n} \Rightarrow \sum_{i\le n}(\psi_i a^i\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)-\psi_i(a+a^2p)\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)$$

$$\Rightarrow \sum_{i\le n}\left(\sum_{k=0}^{i}\psi_{i}a^{i}(x^{(i-1)-k}y^{k}-\sum_{k=0}^{i}\psi_{i}(a+a^p)(x^{(i-1)-k}y^{k}\right)=\sum_{i \le n}\sum_{k=0}^{i}\psi_{i}a^{i}(x^{(i-1)-k}y^{k})-\sum_ {i \le n}\sum_{k=0}^{i}\psi_{i}(a+a^2p)(x^{(i-1)-k}y^{k}) \Longleftrightarrow \left(\sum_{i\le n }\psi_{i}a^{i}\right)\left(\sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right)-\left( \sum_{i\le n}\psi_{i}(a+a^2p)\right)\left(\sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right) $$Sonuç olarak;

$$\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right) \left( \sum_{i\le n}\psi_{i}(a^{i}-(a^2p+a)\right) \equiv 0 \pmod{p^n}$$ bulunur. Burada $2$ farklı durum var.+

$\text{Durum a/1:}$ $$\Rightarrow \sum_{i\le n}\psi_{i}(a(a^{i-1}-ap-1)) \equiv 0 \pmod{p^{n}}$$

$n=1$ için kolayca görülebildiği üzere, $-\psi_{1}a^2p\equiv 0 \pmod p$, Yine aynı şekilde $n=2$ için $\mathbf{Z}_{p^{n}} = \{ 0,1,\dots, p^n-1 \}$ kümesinin tanımı gereği $\psi_{2} \equiv 0 \pmod {p^2}$ olmalıdır. Şimdi bununla alakalı bir iddia ortaya atalım.

$\text{Iddia:}$ $$\sum_{i\le n}\psi_{i}(a(a^{i-1}-ap-1)) \equiv 0 \pmod{p^{n}}$$ kongürüansının çözümü olması için gerek ve yeter şart $\psi_{i} \equiv 0 \pmod {p^{i}}$ olmasıdır.

$\mathcal {Proof:}$ Tümevarımla ilerleyeceğiz. Şimdi $\psi_{1} \equiv 0\pmod p$ ve $\psi_{2} \equiv 0\pmod{p^2}$ denkliklerinin çözümünün olduğunu varsayalım, yani farz edelim ki $\psi_{i} \equiv 0 \pmod{p^{i}}$ denkliğinin çözümü olsun. O halde $\psi_{k+1} \equiv 0 \pmod{p^{k+1}}$  in de çözümü olması gerekir. Şimdi $\psi_{i} \equiv 0 \pmod{p^{i}}$ denkliğinin çözümü $\mathcal{F}$ olsun. $\psi_{k+1}^{\mathcal{F}} \equiv 0 \pmod{p^{k+1}}$ denkliğinin çözümü olması için, ( $\psi_{k}$ sabit olduğundan türevi $0$ ) $p|0$ ve $p^{n+1}|\psi_{k}(\mathcal{F})$ olduğundan bu denkliğinde çözümü vardır. $\square$

Sonuç olarak, $i$ nin alabileceği $p^n$ farklı değer olduğundan en az farklı $p^n$ tane polinom fonksiyon yazılabilir. Şimdi diğer duruma geçelim.

$\text{Durum a/2:}$ $$\left( \sum_{k=0}^{i}x^{(i-1)-k}y^{k}\right) \equiv 0\pmod{p^n} \Rightarrow \sum_{k=0}^{i}a^{i-1-k}(2a+a^2p)^k = \sum_{k=0}^{i}a^{i-1-k}a^{k}(2a+a^2p)^k \Rightarrow \sum_{k=0}^{i}a^{i-1}(2a+a^2p)^k \equiv 0 \pmod{p^n}$$

$$\Rightarrow a^{i-1}\sum_{k=0}^{i}(p^2+2)^k \equiv 0 \pmod{p^n}$$ Burada da $2$ farklı durum var.

$\text{Durum b/1:}$ $p^{n}|a^{i-1}$ ise, $a|p^n$ olması gerekir ki bu durum $\text{Durum a/1 }$ in içinde.

$\text{Durum b/2:}$ $$\sum_{k=0}^{i}(p^2+2)^k \equiv \dfrac{(p^2+2)((p^2+2)^i-1)}{p^2+1} \pmod{p^n}$$ Bu koşul ise $p>2$ olduğunda Her $a,b \in \mathbf{Z}_{p^{n}}$ koşulunu sağlamaz.

Sonuç olarak tanımlanan bu kümede en fazla $p^n$ polinom fonksiyon durumu sağlar.

[ArtOfMathSolving]

Resmi Çözüm:

$i\ge 0$ için $a_i=\dfrac{(1+p)^i-1}{p}$ kabul edelim. Tümevarımla $f(a_i) \equiv i \cdot f(1) \pmod {p^n}$ elde ederiz.

Eğer $p>2$ veya $p=2$ ve $n=1$ ise, \[ a_i \equiv a_j \pmod {p^n} \: \Longrightarrow \: (1+p)^{j-i} \equiv 1 \pmod {p^{n+1}} \: \Longrightarrow \: i \equiv j \pmod {p^n}. \] olacak ve $a_i+a_j+pa_ia_j=a_{i+j}$ eşitliği gerçeklenecektir. $i,j\ge 0$ için fonksiyon $f(a_i) \equiv ic \pmod {p^n}, \: (0 \leq i<p^n),$ şeklinde tanımlı olacak ve $c \in \mathbb{Z}_{p^n}.$ gibi $p^n$ farklı şekilde seçilebilecek.

Eğer $p=2$ ve $n>1$ ise, \[ a_i \equiv a_j \pmod {2^n} \: \Longrightarrow \: 3^{j-i} \equiv 1 \pmod {2^{n+1}} \: \Longrightarrow \: i \equiv j \pmod {2^{n-1}}. \]
$\mathbb{Z}_{p^n} = \{a_i \: : 0 \leq i<2^{n-1}\} \cup \{-a_i-1 \: : 0 \leq i<2^{n-1}\}.$, ayrıca $2f(-1) \equiv f(-1)+f(-1) \equiv f((-1)+(-1)+2(-1)(-1)) \equiv f(0) \equiv 0 \pmod {2^n}.$ eşitliği de olacaktır.

Aynı şekilde $i,j\ge 0$ için, $a_i+a_j+2a_ia_j=a_{i+j}, \: a_i+(-a_j-1)+2a_i(-a_j-1)=-a_{i+j}-1,$ ve $(-a_i-1)+(-a_j-1)+2(-a_i-1)(-a_j-1)=a_{i+j}$ olduğundan fonksiyon $f(a_i) \equiv ic \pmod {2^n}$ şeklinde olacak ve $f(-a_i-1) \equiv ic+d \pmod {2^n}, \: (0\leq i<2^{n-1}),$ ifadesi de doğru olacaktır.                           

 $\square$