wu :: forums - Print Page


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

        riddles >> medium >> Add To Power And Divide, Get Integer?
        
(Message started by: K Sengupta on Aug 6^th, 2007, 8:20am)

Title: Add To Power And Divide, Get Integer?
Post by K Sengupta on Aug 6^th, 2007, 8:20am

Analytically determine whether for every positive integer P, there always exists a positive integer Q such that 3^Q+5 is divisible by 2^P

Title: Re: Add To Power And Divide, Get Integer?
Post by Eigenray on Aug 6^th, 2007, 8:51am

[hide]yes[/hide]:

[hideb]We prove by induction that for P http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 3, there is a Q such that 3^Q+5 is divisible by 2^P, and no larger power.

Suppose that 3^Q + 5 = t*2^P, where t is is odd. Then we need to find Q' = Q+R such that

3^Q' + 5 = 3^R(t*2^P - 5) + 5 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 2^P + (3^R - 1) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 0 mod 2^P+1.

This will happen when 3^R-1 is divisible by 2^P, but no larger power. But the order of 3 mod 2³ is 2, and this implies that, for P http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 3, the order of 3 mod 2^P is 2^P-2. We therefore take Q' = Q + 2^P-2.[/hideb]

Title: Re: Add To Power And Divide, Get Integer?
Post by Eigenray on Aug 6^th, 2007, 9:02am

Another solution:

[hideb]Z_2^P^* = Z_2^(P-2) x Z₂, where the first factor is generated by 5 = (1,0), and the second factor is generated by -1 = (0,1).

Let P http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 3, and let 3 = (a,b). Now, 3 is not a power of 5 mod 4, so b=1. And a can't be even, otherwise we'd have 3 = -5^a = 7 mod 8. So 3 = (a,1), where a is odd. So there is some Q such that Q*a = 1 mod 2^P-2, so 3^Q = (1,1) = -5.[/hideb]