Author |
Topic: Divisibility of a set of 2^m - 1 (Read 374 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Divisibility of a set of 2^m - 1
« on: Apr 6th, 2007, 12:32am » |
 Quote  Modify
|
From Russian Olympiad.
Show that one of the 2k numbers {21-1, 22-1,23-1,...,22k-1} is divisible by 2k+1
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Divisibility of a set of 2^m - 1
« Reply #1 on: Apr 6th, 2007, 1:31am » |
Quote Modify
|
let mk be the first m such that 2m-1 is divided by (2k+1)
Now if 2k+1 is prime let's assume (because it's true but I haven't figured out how to proof it) that mk <= 2k and furthermore 2k+1 divides every 2i*m_k-1
Then we can proof the case were 2k+1 is composite, because we have some a and b such that (2a+1)*(2b+1)=2k+1
and inductively ma <= 2a and mb <= 2b so ma*mb < 4ab < 4ab + 2a+2b = 2k
Moreover we have mk = LCM(ma, mb) which is better than we need.
|
| « Last Edit: Apr 6th, 2007, 1:36am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Divisibility of a set of 2^m - 1
« Reply #2 on: Apr 6th, 2007, 1:41am » |
Quote Modify
|
Doesn't seem so difficult.
Let's consider the sequence
an = 2n-1 for n = 0, 1, 2, ...
Note that
ai = 2·ai-1+1
Consider the residues (mod 2k+1).
Note that no element can have residue 2k:
Suppose ai had residue 2k. Since
ai = 2·ai-1+1
the same is true mod 2k+1.
2k = 2·ai-1 + 1 (mod 2k+1)
2 is inversible, its inverse is k+1
k = ai-1 + (k+1) (mod 2k+1)
add k
2k = ai-1 + (2k+1) = ai-1 (mod 2k+1)
It shows that if one element has residue 2k, all previous elements have the same residue. But we know a0 has residue 0. So, no an has residue 2k.
That means the residues are all between 0 and 2k-1. If we take the an for n=0...2k, we have more values than possible residues, we must have a duplicate among the residues.
If we take 2 elements that have the same residue (and we know they exist)
ai = aj (mod 2k+1), for i<j
then 2k+1 divides aj-ai = (2j-1) - (2i-1) = (2j-i-1)*(2i)
since 2k+1 is odd, 2k+1 divides (2j-i-1).
It is easy to see that j-i>=1 and j-i<=2k.
This proves 2k+1 divides 2n-1 for some n, 1<=n<=2k.
OK, it wasn't THAT easy. I thought it would be a simple pigeonhole principle.
|
| « Last Edit: Apr 6th, 2007, 1:54am by Grimbal » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Divisibility of a set of 2^m - 1
« Reply #3 on: Apr 6th, 2007, 9:52am » |
Quote Modify
|
Well done guys.
Yes, this problem is borderline easy/medium.
Towr's solution is what I had in mind. Completing/Rewriting it:
We use induction.
if 2k+1 is prime or a prime power, then 2phi(2k+1) - 1 is divisible by 2k+1.
(phi(x) is the euler-totient function)
if 2k+1 = XY where X and Y are odd > 1 and relatively prime
then consider x and y such that X | 2x -1 and Y | 2y - 1
It is clear that XY | 2xy - 1
Now we can find x and y such that x <= X-1 and y <= Y - 1
This means that xy <= XY-1 = 2k
|
| « Last Edit: Apr 6th, 2007, 10:07am by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Divisibility of a set of 2^m - 1
« Reply #4 on: Apr 6th, 2007, 10:01am » |
Quote Modify
|
I think I just found a gap in my proof. Let me recheck and try correcting it later...
[edit] I have corrected the above proof, I think [/edit]
Aargh. I just realized. This should have been in easy: if (a,n) =1 then aphi(n) -1 = 0 (mod n). We can apply this directly here
|
| « Last Edit: Apr 6th, 2007, 10:11am by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print