Gönderen Konu: Tübitak Lise 2. Aşama 1996 Soru 5  (Okunma sayısı 5058 defa)

Çevrimdışı Lokman Gökçe

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3.716
  • Karma: +23/-0
  • İstanbul
Tübitak Lise 2. Aşama 1996 Soru 5
« : Ağustos 06, 2013, 03:31:33 öö »
Her $n$ pozitif tam sayısı için $$ \prod\limits_{k=0}^{n-1}{(2^{n}-2^{k})}$$ sayısının $n!$ ile bölündüğünü gösteriniz.
« Son Düzenleme: Eylül 01, 2013, 11:53:29 öö Gönderen: bosbeles »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 2.633
  • Karma: +9/-0
Ynt: 5
« Yanıtla #1 : Ağustos 25, 2013, 10:26:46 öö »
$n!$ sayısındaki $2$ lerin sayısı ile $M = \prod \limits_{k=0}^{n-1} {2^k \left( 2^{n-k} - 1\right)}$ sayısındaki $2$ sayısını karşılaştıralım.

$n!=x\cdot 2^{r} \Rightarrow \max(r) = \lfloor \frac n2 \rfloor + \lfloor \frac n4 \rfloor + \cdots \leq n\left(\frac 12 + \frac 14 + \frac 18 + \cdots \right) = n$.

$M = \prod \limits_{k=0}^{n-1} {2^k \left( 2^{n-k} - 1\right)} = x\cdot 2^r \Rightarrow \max(r) = \sum \limits_{k=0}^{n-1} k = \frac {n(n-1)}{2}$.
$n\geq 3$ için,  $\frac {n(n-1)}{2}\geq n$ olacaktır. Yani $n\geq 3$ için, $M$ sayısında $n!$ dekinden daha fazla (ya da eşit) $2$ çarpanı var.

$M_{n=1} = 1 \Rightarrow 1! \mid 1$ ve $M_{n=2} = 6 \Rightarrow 2! \mid 6$ olduğu için, $n!$ sayısında $M$ dekinden daha fazla $2$ çarpanı yoktur.
Diğer $p>2$ asal sayıları için de aynı sonuca varabiliyorsak $n! \mid M$ diyebiliriz.

$p>2$ bir asal sayı olsun.
$n!=x\cdot p^{r} \Rightarrow \max(r) = \sum \limits_{i=1}^{\infty} \left \lfloor \frac n{p^i} \right \rfloor$.

Euler'in $\varphi$ sinden, $2^{p-1} \equiv 1 \pmod p$ olduğu için $M = \left(2^n - 1\right)\cdot \left(2^{n-1} - 1\right) \cdots \left(2^1 - 1\right) \prod \limits_{k=0}^{n-1} 2^k$ sayısının çarpanlarından $ \left \lfloor \frac n{p-1} \right \rfloor$ tanesi $p$ ile bölünecek.

Benzer şekilde $p^i \mid M $ durumunu incelersek: $\varphi \left( p^i \right) = p^{i-1}(p-1) \Rightarrow 2^{p^{i-1}(p-1)} \equiv 1 \pmod {p^i}$ olduğu için $M$ sayısının çarpanlarından $ \left \lfloor \frac n{p^{i-1}(p-1)} \right \rfloor$ tanesi $p^i$ ile bölünecek.

Bu durumda $M=x\cdot p^r \Rightarrow \max(r) = \sum \limits_{i=1}^{\infty} {\left \lfloor \frac n{p^{i-1}(p-1)} \right \rfloor}$ olacaktır.
Her $i=1,2,\dots$ için $ \left \lfloor \frac n{p^{i-1}(p-1)} \right \rfloor \geq  \left \lfloor \frac n{p{i}} \right \rfloor$ olduğu için $M$ sayısındaki $p$ çarpanlarının sayısı $n!$ sayısındaki $p$ çarpanlarının sayısından az olmayacaktır. Bu durumda $n! \mid M$ dir.
« Son Düzenleme: Haziran 22, 2014, 08:19:42 öö Gönderen: geo »

 


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 35 36 37 
SimplePortal 2.3.3 © 2008-2010, SimplePortal