بزرگترین توان 2 که عدد A بر آن بخشپذیر است

Question

$A= 3^{128} -1$

در صورت امکان اثبات سوال را برای $A= 3^{2^{n} } -1$ هم قرار دهید.

Answer 1

اگر $p$ یک عدد اول و $n$ یک عدد طبیعی باشد، آنگاه بزرگترین عدد صحیح نامنفی مثل $a$ که $p^{a}|n$ را با $E_{p}(n)$ نشان می دهیم. با این مقدمات مسأله مورد نظر معادل است با محاسبه:

$$A_{n} =E_{2}( 3^{ 2^{n} }-1 )$$ که در آن $n$ یک عدد طبیعی است. نشان می دهیم برای هر عدد طبیعی $n$ :

$$A_{n+1}=A_{n}+1$$

داریم:

$$A_{n+1}=E_{2}( 3^{ 2^{n+1} }-1 )=E_{2}( (3^{ 2^{n} }-1)(3^{ 2^{n} }+1) )\,\,\,\,\,\,\,\,\,\,\,\,(1)$$

از آنجا که برای هر عدد اول $p$ و هر دو عدد طبیعی $a,b$ داریم:

$$E_{p}( ab )=E_{p}( a )+E_{p}( b )$$

پس با توجه به $(1)$ داریم:

$$A_{n+1}=E_{2}(3^{ 2^{n} }-1)+E_{2}(3^{ 2^{n} }+1)=A_{n}+E_{2}(3^{ 2^{n} }+1)$$

چون:

$$3^{ 2^{n} }+1 \equiv (-1)^{2^n}+1 \equiv 2\,\,\,(mod\,4)$$ $$3^{ 2^{n} }+1 \equiv (1)^{2^n}+1 \equiv 0\,\,\,(mod\,2)$$

پس $\, E_{2}(3^{ 2^{n} }+1)=1 \,$ بنابراین $\,A_{n+1}=A_{n}+1\,$ و چون:

$$A_{1}=E_{2}( 3^{ 2^{1} }-1 )=E_{2}( 8 )=3$$ پس $\,A_{n}=n+2\,$ به عبارت دیگر برای هر عدد طبیعی $n$ بزرگترین توان $2$ که $\,3^{ 2^{n} }-1\,$ بر آن بخش پذیر است برابر است با $\,n+2\,$ .

مثلاً بزرگترین توان 2 که $\,3^{ 128 }-1\,$ بر آن بخش پذیر است برابر است با $9$ .

سوال خوبی بود ممنون

Answer 2

روش مورد نظر المپیاد: برای $3^{128}-1$ می توان گفت:

$$3^{128}-1=2^3(3^{2}+1)(3^{4}+1)(3^{8}+1)(3^{16}+1)(3^{32}+1)(3^{64}+1)$$

چون همه ی عوامل داخل پرانتز بر $2$ بخشپذیرند ولی بر $4$ بخشپذیر نیستند پس بزرگترین عدد حاصل از توانی از $2$ که $3^{128}-1$ بر آن بخشپذیر است برابر است با:

$$2^3 ( 2 \times 2 \times 2 \times 2 \times 2 \times 2)=2^9$$

پس جواب برابر است با $9$ .