Gönderen Konu: Tübitak Lise 2. Aşama 1993 Soru 6  (Okunma sayısı 2868 defa)

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3192
  • Karma: +22/-0
  • İstanbul
Tübitak Lise 2. Aşama 1993 Soru 6
« : Ağustos 06, 2013, 04:23:26 öö »
Aşağıdaki koşulları sağlayan $n_{1}, n_{2},\ldots n_{k}$ ve $a$ pozitif tamsayıları veriliyor.
  • Her $i\ne j$ için $(n_{i},n_{j})=1$
  • Her $i$ için $a^{n_{i}}\equiv 1 \pmod {n_{i}}$.
  • Her $i$ için $ n_{i} \nmid a-1$
Bu durumda $a^{x}\equiv 1 \pmod x$ denkliğinin gerçekleştiği en az $2^{k+1}-2$ tane $x>1$ tamsayısının bulunduğunu gösteriniz.
« Son Düzenleme: Haziran 21, 2014, 04:00:26 ös Gönderen: geo »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1801
  • Karma: +8/-0
Ynt: Tübitak Lise 2. Aşama 1993 Soru 6
« Yanıtla #1 : Haziran 21, 2014, 09:31:00 ös »
$a^b \equiv 1 \pmod b$, $a^c \equiv 1 \pmod c$ ve $(b,c)=1$ olduğunda $b \mid a^{bc} - 1$ ve $c \mid a^{bc} - 1$, dolayısıyla $bc \mid a^{bc} - 1$ olacaktır.

$x$, herhangi $1\leq m \leq k$ tane farklı $n_i$ sayısının çarpımı olduğunda $n_i$ ler aralarında asal olduğu için $a^x \equiv 1 \pmod x$ olacaktır.

$\alpha$ ve $\beta$, $1,2,\dots, k$ kümesinin sırasıyla $r$ ve $s$ elemanlı permütasyonu olmak üzere; $$n_{\alpha (1)} \cdot n_{\alpha (2)} \cdots n_{\alpha (r)} =  n_{\beta (1)} \cdot n_{\beta (2)} \cdots n_{\beta (s)}$$ olması için $r=s$ ve $\alpha = \beta$ olması gerekir. Aksi halde sol ve sağ taraftaki aynı olan $n_i$ ler sadeleştirildikten sonra geri kalan $n_i$ lerden herhangi biri diğer taraftaki farklı çarpımı bölmek zorunda olduğundan aralarında asallık durumu bozulmuş olur.

O halde, $n_i$ lerin çarpımlarından oluşan kümenin her elemanı $x$ in bir değeri olabilir. Bu şekilde, (boş kümeyi çıkartalım) $2^k - 1$ adet $x$ değeri vardır.

Bu kümenin bir elemanı $b$ olsun. $[a-1, b]=\ell$ ile $(a-1)$ ile $\ell$ sayılarının $\text{okek}$ ini gösterelim. $(a-1)\mid a^{\ell}-1$ ve $b \mid a^{\ell}-1$ olduğu için $\ell \mid a^{\ell} - 1$ dir.

$[a-1, n_i] = \ell_i$ olsun. $\ell_i$ sayılarını önceki kümedeki elemanlarla ve kendi aralarında farklılık açısından karşılaştıracağız.

Bu kümenin $\ell = c$ olacak şekilde bir $c$ elemanı bulunamaz. Çünkü $c$ nin $n_i \nmid b$ olan $n_i$ çarpanı için $n_i \nmid (a-1)$ dolayısıyla da $n_i \nmid \ell$ olacaktır.

Bu kümenin bir $d$ elemanı için $[a-1, d] = u$ olsun. $b\neq d$ olduğunda $\ell = u$ olamaz. Yine benzer şekilde $d$ nin $n_i \nmid b$ olan çarpanı için $n_i \nmid \ell$ olacaktır.

Bu durumda $2 \cdot (2^{k} -1 ) = 2^{k+1}-2$ adet $x$ tam sayısı bulmuş olduk.

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 
SimplePortal 2.3.3 © 2008-2010, SimplePortal