جواب: برای $n$های فرد $k=2$ و برای $n$های زوج $k=1$.
برهان: اول حکم را برای $n$های فرد اثبات میکنیم. چون
$$3^{n}+1=(4)( 3^{n-1}- 3^{n-2} +\cdots+1)$$
و $(3^{n-1}- 3^{n-2} +...+1)$ عددی فرد است پس بزرگترین توان دویی که $ 3^{n}+1 $ را عاد میکند، $ 2^{2} $ است.
اکنون برای $n$های زوج. فرض میکنیم $n=2^{ \alpha } \beta $
که$ \beta$ عددی فرد است و $ \alpha\geq 1 $. پس خواهیم داشت که
$$3^{n}+1=( 3^{2^{ \alpha } }+1)( 3^{2^{ \alpha }( \beta -1)} - 3^{ 2^{ \alpha }(\beta -2)}\cdots+1)$$
که میدانیم $ ( 3^{2^{ \alpha }( \beta -1)} - 3^{ 2^{ \alpha }(\beta -2)}+\cdots+1)$ عددی فرد میشود. پس باید ثابت کنیم که ۴ عدد $3^{2^{ \alpha } }+1 $ را عاد نمیکند. توجه کنید که
$$3^{2} \overset{4}{\equiv} 1\;\Longrightarrow\; 3^{2^\alpha}\overset{4}{\equiv}1$$
پس به روشنی ثابت میشود که ۴ عدد $3^{2^{ \alpha } }+1 $ را عاد نمیکند.
