• [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 ?)

__________________________

Love Theme from Blade Runner Vangelis Cover (with Guitar)

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

--- 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)