# help with proof for number theory, possibly using induction?

• Dec 7th 2012, 06:09 PM
alexer1278
help with proof for number theory, possibly using induction?
If k > 2, and n = 2k-3, show that 3n is not congruent to 1 (mod 2k).
• Jan 1st 2013, 06:59 AM
LordoftheFlies
Re: help with proof for number theory, possibly using induction?
Old thread but if you're still interested: there are several ways to do this.

1) By induction for $\displaystyle n>2:$ assume $\displaystyle 3^{2^{n-3}}\equiv 2^{n-1}+1\pmod{2^n}\iff 3^{2^{n-3}}= 2^{n-1}+1+2^{n}k$

$\displaystyle \Rightarrow\;\; 3^{2^{n-2}}= (2^{n-1}+1+2^{n}k)^2=2^n+1+2^{n+1}(2^{n-3}+2^{n-1}k+2^{n-1}k^2)$

$\displaystyle \iff 3^{2^{n-2}}\equiv 2^{n}+1\pmod{2^{n+1}}$ etc.

2) A rather nice way is to consider $\displaystyle 3^{2^{n-3}}-1=(3^2-1)(3^2+1)(3^4+1)\cdots (3^{2^{n-4}}+1)=2^3 \cdot\displaystyle\prod_1^{n-4} (3^{2^k}+1)$
$\displaystyle 3^2\equiv 1\pmod{4}\Rightarrow 3^{2^k}\equiv 1\pmod{4}\Leftrightarrow 3^{2^k}+1\equiv 2\pmod{4}$ therefore the highest power of 2 dividing $\displaystyle 3^{2^k}+1$ is 2

It follows that $\displaystyle 2^{n-1}$ is the highest power of 2 dividing $\displaystyle \displaystyle 2^3\cdot \prod_1^{n-4} (3^{2^k}+1)$, so $\displaystyle 2^n$ cannot divide $\displaystyle 3^{2^{n-3}}-1$