congruence modulo 2^n

**stumped765** · November 3rd 2009, 06:34 PM

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.

**Bruno J.** · November 3rd 2009, 06:47 PM

It holds for $n=3$ ; I'll let you prove that. Suppose it holds up to $n-1$ . Note that $x^{2^{n-2}}-1=(x^{2^{n-3}}-1)(x^{2^{n-3}}+1)$ ; and by the induction hypothesis, $x^{2^{n-3}}-1$ is divisible by $2^{n-1}$ , and since $x$ is odd, $x^{2^{n-3}}+1$ is divisible by 2 so $(x^{2^{n-3}}-1)(x^{2^{n-3}}+1)=x^{2^{n-2}}-1$ is divisible by $2^n$ .

Thread: congruence modulo 2^n

LinkBack

Thread Tools

Display

congruence modulo 2^n

Similar Math Help Forum Discussions

[SOLVED] Modulo and congruence

congruence modulo twenty four

congruence property modulo p^2

congruence modulo m

congruence modulo m

Search Tags