Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4839. (December 2016)

B. 4839. Solve the following equation in the set of positive integers:

\(\displaystyle n!= 2^a - 2^b. \)

(Proposed by K. Williams, Szeged)

(6 pont)

Deadline expired on January 10, 2017.


Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Mivel \(\displaystyle 0<n!\), ezért \(\displaystyle a> b\), legyen \(\displaystyle d=a-b> 0\). Ekkor az egyenlet \(\displaystyle n!=2^b(2^d-1)\) alakban írható. Jelölje \(\displaystyle \nu_3(m)\) azt, hogy az \(\displaystyle m\) szám prímtényezős alakjában mi a 3 kitevője. Ha \(\displaystyle 9\leq n\), akkor \(\displaystyle \nu_3(n!)\geq \frac{n}{3}\), hiszen az \(\displaystyle 1\cdot 2\cdot \dots \cdot n\) szorzatban a 3-mal osztható tényezők száma \(\displaystyle \lceil n/3\rceil\) és \(\displaystyle n\geq 9\) esetén szerepel a 9 is, ami már \(\displaystyle 3^2\)-nel is osztható. Ezért \(\displaystyle \nu_3(2^b(2^d-1))=\nu_3(2^d-1)\) értéke is legalább \(\displaystyle n/3\). Megmutatjuk, hogy \(\displaystyle 2^d-1\) pontosan akkor osztható 3-mal, ha \(\displaystyle d\) páros, és ekkor \(\displaystyle \nu_3(2^d-1)=\nu_3(d)+1\). Az állítást \(\displaystyle \nu_3(d)=\alpha\) szerinti teljes indukcióval bizonyítjuk. Vizsgáljuk meg a 2-hatványok 9-es maradékát:

\(\displaystyle 2^0\equiv 1, 2^1\equiv 2, 2^2\equiv 4, 2^3\equiv 8, 2^4\equiv 7, 2^5\equiv 5, 2^6\equiv 1,\dots\)

és innen ciklikusan ismétlődik az \(\displaystyle 1,2,4,8,7,5\). Ebből egyrészt következik, hogy \(\displaystyle 2^d-1\) pontosan akkor osztható 3-mal, ha \(\displaystyle d\) páros, másrészt az is, hogy \(\displaystyle 2^d-1\) pontosan akkor osztható \(\displaystyle 3^2\)-tel is, ha a páros \(\displaystyle d\) kitevő 3-mal is osztható. Legyen tehát \(\displaystyle d=2\cdot 3^\alpha\cdot D\), ahol \(\displaystyle 3\nmid D\). Azt kell megmutatnunk, hogy \(\displaystyle \nu_3(2^d-1)=\alpha+1\), és már láttuk, hogy \(\displaystyle \alpha=0\) esetén ez teljesül. Most megmutatjuk indukcióval, hogy ha az állítás teljesül \(\displaystyle \alpha-1\)-re, akkor \(\displaystyle \alpha\)-ra is. Tekintsük a következő szorzattá alakítást:

\(\displaystyle 2^d-1=2^{2\cdot 3^\alpha\cdot D}-1=(2^{2\cdot 3^{\alpha-1}\cdot D}-1)(2^{4\cdot 3^{\alpha-1}\cdot D}+2^{2\cdot 3^{\alpha-1}\cdot D}+1).\)

Legyen \(\displaystyle c=2^{2\cdot 3^{\alpha-1}\cdot D}\). Megmutatjuk, hogy \(\displaystyle \nu_3(c^2+c+1)=1\). Ehhez azt kell belátnunk, hogy \(\displaystyle 3|c^2+c+1\), de \(\displaystyle 9\nmid c^2+c+1\). Mivel \(\displaystyle c=2^{2\cdot 3^{\alpha-1}\cdot D}\)-ben a kitevő páros, ezért a korábbiak szerint \(\displaystyle 3|(c-1)\), vagyis \(\displaystyle c=3k+1\) alakú (ahol \(\displaystyle k\) nemnegatív egész szám). Ekkor \(\displaystyle c^2+c+1=(3k+1)^2+(3k+1)+1=9(k^2+k)+3\), vagyis valóban \(\displaystyle \nu_3(c^2+c+1)=1\). így az indukciós feltevést is használva:

\(\displaystyle \nu_3(2^d-1)=\nu_3(2^{2\cdot 3^{\alpha-1}\cdot D}-1)+\nu_3(2^{4\cdot 3^{\alpha-1}\cdot D}+2^{2\cdot 3^{\alpha-1}\cdot D}+1)=\alpha+\nu_3(c^2+c+1)=\alpha+1,\)

vagyis az állítás \(\displaystyle \alpha\)-ra is igaz. Tehát \(\displaystyle \nu_3(2^d-1)=\nu_3(d)+1\), ha \(\displaystyle d\) páros. Tegyük fel, hogy \(\displaystyle 9\leq n\). Az eddigiek szerint \(\displaystyle \nu_3(2^d-1)\geq \frac{n}{3}\), vagyis \(\displaystyle \nu_3(d)\geq \frac{n}{3}-1\). Mivel \(\displaystyle 3|2^d-1\) miatt \(\displaystyle d\)-nek párosnak is kell lennie, ezért \(\displaystyle d\geq 2\cdot 3^{\frac{n}{3}-1}\). Mivel \(\displaystyle 2^d-1\leq 2^b(2^d-1)=n!\) és \(\displaystyle n!\) páros, ezért \(\displaystyle 2^d\leq n!\) is teljesül, és ezért

\(\displaystyle 2^{2\cdot 3^{\frac{n}{3}-1}}\leq n!\leq n^n.\)

Ebből 2-es alapú logaritmust véve:

\(\displaystyle 2\cdot 3^{\frac{n}{3}-1} \leq n\log_2 n. \)

Ha \(\displaystyle n=12\), akkor ez már nem teljesül, mert a bal oldal értéke 54, a jobb oldal pedig 44-nél is kisebb. Megmutatjuk, hogy más \(\displaystyle n\geq 12\) esetén sem teljesül. Ehhez elég megmutatnunk, hogy ha valamely \(\displaystyle n\geq 12\)-re \(\displaystyle 2\cdot 3^{\frac{n}{3}-1} > n\log_2 n\), akkor \(\displaystyle 2\cdot 3^{\frac{n+1}{3}-1} > (n+1)\log_2 (n+1)\). Ezt a következő becslések segítségével bizonyíthatjuk:

\(\displaystyle (n+1)\log_2 (n+1)= n(\log_2 n)(1+1/n)\frac{\log_2 n+\log_2(1+1/n)}{\log_2 n}\leq\)

\(\displaystyle \leq n(\log_2 n) (1+1/12)\frac{\log_2 n+\log_2(1+1/12)}{\log_2 n}\leq \)

\(\displaystyle \leq n(\log_2 n) (1+1/12)\frac{\log_2 12+\log_2(1+1/12)}{\log_2 12}<1,2\cdot n(\log_2 n)<\)

\(\displaystyle <3^{1/3}\cdot 2\cdot 3^{\frac{n}{3}-1}= 2\cdot 3^{\frac{n+1}{3}-1}. \)

Tehát azt kaptuk, hogy \(\displaystyle n\geq 12\) esetén az \(\displaystyle n!=2^b(2^d-1)\) egyenletnek nincs megoldása. Ha \(\displaystyle n!=2^b(2^d-1)\), akkor \(\displaystyle 2^b\) az \(\displaystyle n!\) szám legnagyobb 2-hatvány osztója, \(\displaystyle 2^d-1\) pedig az \(\displaystyle n!\) szám páratlan része. így \(\displaystyle 1\leq n\leq 11\) esetén azt kell megvizsgálnunk, hogy \(\displaystyle n!\) páratlan részéhez 1-et adva mikor kapunk 2-hatványt. Az \(\displaystyle n=1,2,\dots,11\) esetekben az \(\displaystyle n!\) szám páratlan része rendre:

\(\displaystyle 1,1,3,3,15,45, 315,315,2835,14175,155925.\)

A páratlan résznél 1-gyel nagyobb szám pontosan az első 5 esetben 2-hatvány, így az egyenletnek pontosan akkor van nemnegatív egész megoldása, ha \(\displaystyle 1\leq n\leq 5\). Vizsgáljuk meg mind az öt esetet:

– Ha \(\displaystyle n=1\), akkor \(\displaystyle n!=1\), ezért \(\displaystyle 2^b=1\) és \(\displaystyle 2^d-1=1\), amiből \(\displaystyle a=1,b=0\) (\(\displaystyle d=1\)), vagyis itt nem kapunk megoldást, mert \(\displaystyle b\) nem pozitív.

–Ha \(\displaystyle n=2\), akkor \(\displaystyle n!=2\), ezért \(\displaystyle 2^b=2\) és \(\displaystyle 2^d-1=1\), amiből \(\displaystyle a=2,b=1\) (\(\displaystyle d=1\)).

–Ha \(\displaystyle n=3\), akkor \(\displaystyle n!=6\), ezért \(\displaystyle 2^b=2\) és \(\displaystyle 2^d-1=3\), amiből \(\displaystyle a=3,b=1\) (\(\displaystyle d=2\)).

–Ha \(\displaystyle n=4\), akkor \(\displaystyle n!=24\), ezért \(\displaystyle 2^b=8\) és \(\displaystyle 2^d-1=3\), amiből \(\displaystyle a=5,b=3\) (\(\displaystyle d=2\)).

–Ha \(\displaystyle n=5\), akkor \(\displaystyle n!=120\), ezért \(\displaystyle 2^b=8\) és \(\displaystyle 2^d-1=15\), amiből \(\displaystyle a=7,b=3\) (\(\displaystyle d=4\)).

Az egyenlet megoldásai tehát: \(\displaystyle (n=2;a=2,b=1),(n=3;a=3,b=1),(n=4;a=5,b=3),(n=5;a=7,b=3)\).


Statistics:

34 students sent a solution.
6 points:Borbényi Márton, Döbröntei Dávid Bence, Gáspár Attila, Győrffy Ágoston, Kerekes Anna, Kovács 246 Benedek, Matolcsi Dávid, Sokvári Olivér, Tóth Viktor, Weisz Máté.
5 points:Csahók Tímea, Daróczi Sándor, Németh 123 Balázs, Saár Patrik.
3 points:1 student.
1 point:16 students.
0 point:3 students.

Problems in Mathematics of KöMaL, December 2016