1763s+13

[enzocreti]

consider numbers of the form 1763s+13 with s some non-negative integer


Is (1763+13) the only number of the form 1763s+13 such that (1763s+13)/111 is a power of 2?

[fivemack]

Originally Posted by enzocreti

consider numbers of the form 1763s+13 with s some non-negative integer


Is (1763+13) the only number of the form 1763s+13 such that (1763s+13)/111 is a power of 2?

No, obviously not: phi(1763)=1680 so 111*2^{1680n+4} will be congruent to 13 mod 1763 for all n.

In fact 111*2^{140n+4} is congruent to 13 mod 1763 for all n.

? 1404074144660748252246434899752676192378801*1763+13-111*2^144
%10 = 0

[LaurV]

I bet he somehow found that by mistake (or by whatever numerology stuff he's usually doing), and then he ran some pari script or equivalent, to 10^10 or so, which ran at least one overnight, before asking this interesting question...

[Dr Sardonicus]

Originally Posted by LaurV

I bet he somehow found that by mistake (or by whatever numerology stuff he's usually doing), and then he ran some pari script or equivalent, to 10^10 or so, which ran at least one overnight, before asking this interesting question...

I vote for "whatever numerology." Note that 1763 = 41*43. I seem to recall his having touted the factors in his posts before.

I further note that, armed with these small factors, the multiplicative order of 2 (mod 1763) can easily be found by hand. We have 2^10 = 1024, so 2^10 + 1 = 1025 = 25*41. The multiplicative order of 2 (mod 41) is thus easily seen to be 2*10, or 20. Similarly, 2^7 + 1 = 129 = 3*43, so the multiplicative order of 2 (mod 43) is 2*7, or 14. The multiplicative order of 2 (mod 41*43) is then the lcm of 2*10 and 2*7, or 2*10*7 = 140.

[LaurV]

It seems a bit odd (for who doesn't know) where did you get your starting numbers from (like, why 2^10?). For these small (odd) numbers there is a simple calculus, which may take longer, but it is so simple you can do it in your mind:
1. start with 1
2. add n
3. divide by 2 as long as possible, keep track of how many divisions you did
4. repeat from step 2 until you get 1
(you will always get 1. Why?)

Ex: from 41 (in parenthesis the number of divisions):

1, 42(1), 21, 62(2), 31, 72(3), 36(4), 18(5), 9, 50(6), 25, 66(7), 33, 74(8), 37, 78(9), 39, 80(10), 40(11), 20(12), 10(13), 5, 46(14), 23, 64(15), 32(16), 16(17), 8(18), 4(19), 2(20), 1

from 43:

1, 44(1), 22(2), 11, 54(3), 27, 70(4), 35, 78(5), 39, 82(6), 41, 84(7), 42(8), 21, 64(+6=14),

With a bit of practice, you can shorten this a lot, as the divisibility with powers of two is given by last digits of the number (in fact, I already shortened the last example by exploiting that 64 is 2^6).

When pencil and paper is available, you can do this much faster by writing the initial numbers in binary, because addition is way simpler, and division by 2 is just ignoring the tailing zeros. At the end, you count the zeros. Ex, 43 is 8*5+3, so it is 5 (101 binary) shifted with 3 positions to the left (8=2^3), and added 3 (11 binary), i.e. 101011. Do the same calculus as above in binary and at the end count the tailing zeros:

 
                 1  |(1) 
           101011  |(43) 
           ------  | 
           101100  |(44->11) 
         101011    | 
         ------    | 
         110110    |(54->27) 
        101011     | 
        ------     | 
       1000110     |(70->35) 
       101011      | 
        ------      | 
       1001110      |(78->39) 
      101011       | 
       ------       | 
     1010010       |(82->41) 
     101011        | 
     ------        | 
    1010100        |(84->21)
   101011          | 
   ------          | 
  1000000          |(64->1) 
 -------------------------------- 
  Total 14 zeros 

Disclaimer: this post was written without help from any pencil, paper, or calculator of any kind
Edit 5 times, hating that f'king alignment... added decimal for alignment purpose, if you see the decimal numbers misaligned, then the forum fucd with me again...
Gave up after 521st edit. Make whatever you want of it...

[Dr Sardonicus]

Originally Posted by LaurV

It seems a bit odd (for who doesn't know) where did you get your starting numbers from (like, why 2^10?).

I reasoned as follows: phi(41) = 41 - 1 = 40. Since 8 divides 40, 2 is a quadratic residue (mod 41), i.e. 2^20 == 1 (mod 41). Thus 2^10 == 1 or -1 (mod 41). But 2^10 - 1 = (2^5 - 1)*(2^5 + 1), both factors being less than 41. (Note that 1 < 2^4 < 41 so the multiplicative order does not divide 4).

Similarly, 43 - 1 = 42 - 2*3*7, so 2^42 == 1 (mod 43), but here 2 is a quadratic non-residue (mod 43), so the multiplicative order does not divide 3*7 = 21.

We turn to 2*3 and 2*7. Clearly 2^6 = 64 is not congruent to 1 (mod 43). If 2^14 == 1 (mod 43) then 2^7 == 1 or -1 (mod 43). We know that 2^7 - 1 is prime, so not divisible by 43. Checking 2^7 + 1 we find that it is indeed divisible by 43.

The prime 43 is also small enough for easy application of the classical criterion for 2 being a cubic residue (mod p), p = x^2 + 27*y^2: 43 = 4^2 + 27*1^2, whence 2^(42/3) == 1 (mod 43).