All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Maximum Power 2 Divide Evenly (Posted on 2008-10-19)
Determine the maximum value of a positive integer G, such that (20071024 -1) is evenly divisible by 2G.

Note: Try to solve this problem analytically, although computer program/ spreadsheet solutions are welcome.

 See The Solution Submitted by K Sengupta Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution | Comment 1 of 2

In order for 2007^1024 - 1 to be evenly divisible by 2^G, 2007^1024 must be congruent to 1 mod 2^G. So just do the power raising mod 2^G for various G's until you no longer get 1. For manual processing this could be done by squaring 10 times for each 2^G value, but using the computer, modular multiplication by 2007, 1024 times is no big deal:

DEFDBL A-Z
p = 1
FOR g = 1 TO 20
p = p * 2
v = 1
FOR i = 1 TO 1024
v = (v * 2007) MOD p
NEXT
PRINT USING "## ####### #######"; g; p; v
NEXT

The resulting table is:

` G     2^G  2007^1024 mod 2^G  -    ----  -----------------    1       2            1 2       4            1 3       8            1 4      16            1 5      32            1 6      64            1 7     128            1 8     256            1 9     512            110    1024            111    2048            112    4096            113    8192            114   16384         819315   32768         819316   65536         819317  131072         819318  262144         819319  524288       27033720 1048576       794625`

So 13 is the maximum allowable positive integer value of G.

And, of course, as 2007^1024-1 is not divisible by 2^14, it's not divisible by any larger value of 2^G.

 Posted by Charlie on 2008-10-19 14:36:08

 Search: Search body:
Forums (0)