wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Divisibility of a set of 2^m - 1
        
(Message started by: Aryabhatta on Apr 6^th, 2007, 12:32am)

Title: Divisibility of a set of 2^m - 1
Post by Aryabhatta on Apr 6^th, 2007, 12:32am

From Russian Olympiad.

Show that one of the 2k numbers {2¹-1, 2²-1,2³-1,...,2^2k-1} is divisible by 2k+1

Title: Re: Divisibility of a set of 2^m - 1
Post by towr on Apr 6^th, 2007, 1:31am

[hide]let m_k be the first m such that 2^m-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 m_k <= 2k and furthermore 2k+1 divides every 2^i*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 m_a <= 2a and m_b <= 2b so m_a*m_b < 4ab < 4ab + 2a+2b = 2k

Moreover we have m_k = LCM(m_a, m_b) which is better than we need.
[/hide]

Title: Re: Divisibility of a set of 2^m - 1
Post by Grimbal on Apr 6^th, 2007, 1:41am

Doesn't seem so difficult.
[hide]
Let's consider the sequence
a_n = 2ⁿ-1 for n = 0, 1, 2, ...
Note that
a_i = 2·a_i-1+1
Consider the residues (mod 2k+1).

Note that no element can have residue 2k:
Suppose a_i had residue 2k. Since
a_i = 2·a_i-1+1
the same is true mod 2k+1.
2k = 2·a_i-1 + 1 (mod 2k+1)
2 is inversible, its inverse is k+1
k = a_i-1 + (k+1) (mod 2k+1)
add k
2k = a_i-1 + (2k+1) = a_i-1 (mod 2k+1)

It shows that if one element has residue 2k, all previous elements have the same residue. But we know a₀ has residue 0. So, no a_n has residue 2k.

That means the residues are all between 0 and 2k-1. If we take the a_n 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)
a_i = a_j (mod 2k+1), for i<j
then 2k+1 divides a_j-a_i = (2^j-1) - (2ⁱ-1) = (2^j-i-1)*(2ⁱ)
since 2k+1 is odd, 2k+1 divides (2^j-i-1).

It is easy to see that j-i>=1 and j-i<=2k.

This proves 2k+1 divides 2ⁿ-1 for some n, 1<=n<=2k.
[/hide]
OK, it wasn't THAT easy. I thought it would be a simple pigeonhole principle.

Title: Re: Divisibility of a set of 2^m - 1
Post by Aryabhatta on Apr 6^th, 2007, 9:52am

Well done guys.

Yes, this problem is borderline easy/medium.

Towr's solution is what I had in mind. Completing/Rewriting it:

[hide]

We use induction.
if 2k+1 is prime or a prime power, then 2^phi(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 | 2^x -1 and Y | 2^y - 1

It is clear that XY | 2^xy - 1
Now we can find x and y such that x <= X-1 and y <= Y - 1

This means that xy <= XY-1 = 2k

[/hide]

Title: Re: Divisibility of a set of 2^m - 1
Post by Aryabhatta on Apr 6^th, 2007, 10:01am

~~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: [hide] if (a,n) =1 then a^phi(n) -1 = 0 (mod n). We can apply this directly here [/hide]