Let x be an ODD integer show that for n>=3

x^2^(n-2) is congruent to 1 (mod 2^n)

Sorry about the superscripts I dont use the computer for math often.

Printable View

- Nov 3rd 2009, 06:34 PMstumped765congruence modulo 2^n
Let x be an ODD integer show that for n>=3

x^2^(n-2) is congruent to 1 (mod 2^n)

Sorry about the superscripts I dont use the computer for math often. - Nov 3rd 2009, 06:47 PMBruno J.
It holds for $\displaystyle n=3$; I'll let you prove that. Suppose it holds up to $\displaystyle n-1$. Note that $\displaystyle x^{2^{n-2}}-1=(x^{2^{n-3}}-1)(x^{2^{n-3}}+1)$; and by the induction hypothesis, $\displaystyle x^{2^{n-3}}-1$ is divisible by $\displaystyle 2^{n-1}$, and since $\displaystyle x$ is odd, $\displaystyle x^{2^{n-3}}+1$ is divisible by 2 so $\displaystyle (x^{2^{n-3}}-1)(x^{2^{n-3}}+1)=x^{2^{n-2}}-1$ is divisible by $\displaystyle 2^n$.