$0\leq a<2^{2008}$ ve $0\leq b<8$ tam sayıları $7(a+2^{2008}b)\equiv 1(mod2^{2011})$ denkliğini sağlıyorsa $b$ nedir?

Question

Bu soru $UMO$  2011 sorusudur. Bu soruya verilen çözüm şöyle:

Answer 1

$2^{2008}|7a-1 \Rightarrow a=\frac{3.2^{2008}+1}{7} \Rightarrow 3.2^{2008}+1+2^{2008}7b\equiv 1(mod2^{2011})  \Rightarrow 3+7b\equiv 0(mod8) \Rightarrow b=3$

Verilen çözüm böyle.Benim bu çözüme itirazım var. Şöyle ki:

$2^{2008}|7a-1 \Rightarrow 7a-1=k.2^{2008} (k\in Z^+)$

Buradan    $a=\frac{k.2^{2008}+1}{7}$ bunun verilen ilk dnklikte yerine yazılması ile:

$k.2^{2008}+1+2^{2008}7b\equiv 1(mod2^{2011}) \Rightarrow (k+7b)2^{2008}\equiv 0(mod2^{2011})$ ve buradan da

$k+7b\equiv0(mod2^n),n\geq 3..........(1)$  veya

$k+7b\equiv0(mod8)...........(2)$ olmalıdır.

$(1)$ denkliğini sağlayan $(k,b,n)$ sıralıları:$(1,1,3) ,(2,2,4),(4,4,5)$

$(2)$ denkliğini sağlayan $(k,b)$ ikilileri:$(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7)$ dir.

yukarıdaki çözümde neden sadece $k=3$ alınmış acaba?

Comments

Haklısınız. $a=\frac{3\cdot2^{2008}+1}7$ eşitliğinde, 3 sayısının nereden geldiği

(yani niçin $7a-1=3\cdot2^{2008}$ olması gerektiği) belirtilmemiş.

Onu açıklanması gerekirdi.

---

Nedeni şu (aslında sorunun ilginç kısmı burası bence)

$7a=k\,2^{2008}+1$ eşitliğinde, $0\leq a<2008$ olduğu için $1\leq k\leq6$ olmalıdır. ( $k$ nın 0  olamayacağı apaçık)

$7a=2k\, 2^{2007}+1=2k\,8^{669}+1$ olur.

$7a$ sayısını $8$ tabanında yazdığımızda, basamakları toplamı (aynen $10$ tabanında $9$ a bölünebilme kuralında olduğu gibi) $7$ ile bölünebilmek zorundadır.

$2k=2,4,6,8,10$ veya $12$ dir.

Bunları 8 tabanında yazarsak $(2)_8,(4)_8,(6)_8,(10)_8,(12)_8,(14)_8$ olur.

Şimdi $2k\,8^{669}+1$ sayısının 8 tabanında yazılışına bakalım:

$k=1$ iken $2k\,8^{669}+1=(20\cdots001)_8$

$k=2$ iken $2k\,8^{669}+1=(40\cdots001)_8$

$k=3$ iken $2k\,8^{669}+1=(60\cdots001)_8$

$k=4$ iken $2k\,8^{669}+1=(10\cdots001)_8$

$k=5$ iken $2k\,8^{669}+1=(120\cdots001)_8$

$k=6$ iken $2k\,8^{669}+1=(140\cdots001)_8$

Bunlardan sadece $k=3$ iken basamaklar toplamının 7 ile bölünebileceği (tam 7 oluyor) görülür.

---

Şöyle daha kısa:

$7a=k\,2^{2008}+1$ oluşundan:

$k\,2^{2008}\equiv 6 \mod 7$

$2^3=8$ ve $8\equiv1\mod 7$

$2^{2008}=2\cdot(2^3)^{669}\equiv2\mod7$

Buradan $2k\equiv6\mod7$ ve ($2$ ile $7$ aralarında asal olduğu için) $k\equiv3\mod7$ bulunur.

$1\leq k\leq6$ olduğu için de $k=3$ olmak zorundadır.

---

Teşekkürler Doğan hocam.