2¹⁰ⁿ -1 divisible by 11

By John Deer on Wednesday, March 27, 2002 - 03:55 am:

Can anybody suggest a simple proof that shows that (2¹⁰ⁿ )-1 is always divisible by 11 for integer n> 0.

By Graeme Mcrae on Wednesday, March 27, 2002 - 07:45 am:

Well, it's true when n=1; 2^10-1=1023=11*93
Assume it's true for x=2^(10k)-1
2^(10(k+1))-1 = (x+1)(2^10)-1 = (x+1)(1024)-1 =
1024x+1023
1024x is divisible by 11 because x is divisible by 11;
1023 is divisible by 11
so 1024x+1023 is divisible by 11
so 2^(10(k+1))-1 is divisible by 11

By Julian Pulman on Wednesday, March 27, 2002 - 11:46 am:

another way is via modular arithmetic:

2^{10 n} - 1 = 32^{2 n} - 1 \equiv 10^{2 n} - 1 (\mod 11) \equiv (- 1)^{2 n} - 1 (\mod 11) \equiv 1^{n} - 1 (\mod 11) \equiv 0 (\mod 11)

Hence, Modulo 11, there is no remainder, so 2¹⁰ⁿ - 1 is always divisible by 11 for all n.

By Andre Rzym on Wednesday, March 27, 2002 - 01:00 pm:

Another way is to observe that:

aⁿ -1=(a-1)(a^n-1 +...+1)

Substitute

a=2¹⁰

and noting that 2¹⁰ -1 is divisible by 11 and you are done.

Andre

By David Loeffler on Wednesday, March 27, 2002 - 11:32 pm:

Just to add yet another solution, there's a result called Fermat's little theorem that implies that a¹⁰ - 1 is always divisible by 11 if a isn't a multiple of 11. Set a = 2ⁿ and you're done.

David

By Andre Rzym on Thursday, March 28, 2002 - 09:15 am:

Just for the avoidance of doubt, David's proof is dependent upon 11 being a prime number.

Andre

By John Deer on Thursday, March 28, 2002 - 11:02 pm:

Many thanks to everyone who contributed to this thread. I did not expect so many interesting and varied solutions to this problem.

John