• [Powers of 2] (mod N) -- puzzles

    From henhanna@gmail.com@21:1/5 to All on Sun Jun 12 18:51:44 2022
    At least one of these is a Nice puzzle.


    2 ^ 100 --- What is it mod 2016 ?



    2 ^ 2022 --- What are the least 2 digits?
    (or ... What is it mod 100 ?)


    __________________________

    https://www.youtube.com/watch?v=PQcwX5yz5No
    Love Theme from Blade Runner Vangelis Cover (with Guitar)


    Blade Runner Blues https://www.youtube.com/watch?v=RScZrvTebeA


    Tao of Love https://www.youtube.com/watch?v=yNtX2T49TDI

    https://www.youtube.com/watch?v=ULJ2s4pdK9E

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Phil Carmody@21:1/5 to henh...@gmail.com on Thu Jun 16 16:02:48 2022
    "henh...@gmail.com" <henhanna@gmail.com> writes:
    At least one of these is a Nice puzzle.

    Different shortcuts make them very easy to do manually.

    2 ^ 100 --- What is it mod 2016 ?

    2016 = 2*1008 = 4*504 = 8*252 = 16*126 = 32*63
    so we only need to calculate 2^100 mod 63, the mod 32 bit's easy
    2^6=64 == 1, so 2^96 == 1
    2^100 == 2^4 * 2^96 == 2^4 == 16 (mod 63)
    16 != 0 mod 32 so add a multiple of 63 to correct that
    63 == -1 (mod 32), so we want 16+16*63 = 16*64 = 1024
    2^100 == 1024 (mod 2016)

    2 ^ 2022 --- What are the least 2 digits?
    (or ... What is it mod 100 ?)

    powers of 2 mod 25 go:
    1, 2, 4, 8, 16, 7, 14, 3, 6, 12, -1, ... it's a primitive root, period 20
    2022 = 101*20+2 so we want 2^2 == 4 (mod 25)
    conveniently, 4 == 0 mod 4
    so 2^2022 == 4 mod (100)

    GP verification once the manual graft's done:
    ? Mod(2,2016)^100
    Mod(1024, 2016)
    ? Mod(2,100)^2022
    Mod(4, 100)

    Phil
    --
    We are no longer hunters and nomads. No longer awed and frightened, as we have gained some understanding of the world in which we live. As such, we can cast aside childish remnants from the dawn of our civilization.
    -- NotSanguine on SoylentNews, after Eugen Weber in /The Western Tradition/

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Gareth Taylor@21:1/5 to henh...@gmail.com on Thu Jun 16 15:04:52 2022
    In article <2993bdc7-2af6-4bdc-be83-bf4eae529600n@googlegroups.com>, henh...@gmail.com <henhanna@gmail.com> wrote:

    2 ^ 100 --- What is it mod 2016 ?

    Use that 2016 = 2^5 x 63.

    And 2^6 == 1 mod 63, so 2^90 == 1 mod 63, so 2^100 == 2^10 mod 2016.

    Slightly differently, notice that 2048 = 2016 + 32. So 2^11 == 2^5 mod
    2016, so we can throw away 2s in sixes as long as we have at least
    eleven left. I.e., 2^100 == (2^6)^15 x 2^10 == 2^10 == 1024 mod 2016.

    2 ^ 2022 --- What are the least 2 digits?

    phi(25) = 20, so 2^2020 == 1 mod 25, so 2^2022 == 04 mod 100.

    Gareth

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From henhanna@gmail.com@21:1/5 to Phil Carmody on Thu Jun 16 12:33:58 2022
    On Thursday, June 16, 2022 at 6:18:58 AM UTC-7, Phil Carmody wrote:
    "henh...@gmail.com" <henh...@gmail.com> writes:
    At least one of these is a Nice puzzle.
    Different shortcuts make them very easy to do manually.
    2 ^ 100 --- What is it mod 2016 ?
    2016 = 2*1008 = 4*504 = 8*252 = 16*126 = 32*63
    so we only need to calculate 2^100 mod 63, the mod 32 bit's easy
    2^6=64 == 1, so 2^96 == 1
    2^100 == 2^4 * 2^96 == 2^4 == 16 (mod 63)
    16 != 0 mod 32 so add a multiple of 63 to correct that
    63 == -1 (mod 32), so we want 16+16*63 = 16*64 = 1024
    2^100 == 1024 (mod 2016)
    2 ^ 2022 --- What are the least 2 digits?
    (or ... What is it mod 100 ?)
    powers of 2 mod 25 go:
    1, 2, 4, 8, 16, 7, 14, 3, 6, 12, -1, ... it's a primitive root, period 20 2022 = 101*20+2 so we want 2^2 == 4 (mod 25)
    conveniently, 4 == 0 mod 4
    so 2^2022 == 4 mod (100)

    GP verification once the manual graft's done:
    ? Mod(2,2016)^100
    Mod(1024, 2016)
    ? Mod(2,100)^2022
    Mod(4, 100)

    Phil


    thanks! is GP a computer language? i can't find it on the Net
    https://en.wikipedia.org/wiki/GP



    Are there some well-known (or simpler) problems of this kind ?

    2 ^ 100 --- What is it mod 2016 ?

    2 ^ 2022 --- What are the least 2 digits?
    (or ... What is it mod 100 ?)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)