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 1
10 1024 1
11 2048 1
12 4096 1
13 8192 1
14 16384 8193
15 32768 8193
16 65536 8193
17 131072 8193
18 262144 8193
19 524288 270337
20 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 |
computer solution
