For you math geeks out there...

[travis2]

First, factor 763,265 in binary:

2^20 = (2^10)^2 = 1024^2 = (1000+24)(1000+24) = 1,000,000 + 2 * 24,000 + 24^2
= 1,048,000 + 24^2 = 1,048,000 + (20+4)(20+4) = 1,048,000 + (400+ 2 *4 * 20 + 16)
= 1,048,000 + (400 + 160 + 16) = 1,048,576 > 763,265

2^10 = 1024 < 763,265

2^15 = 2^10 * 2^5 = 1024 * 32 = (1000+24)*(30+2) = 30,000 + 2000 + 720 + 48
= 32,768 < 763,265

2^17 = 2^15 * 2^2 = 32,768 * 4 = 32,768 * (2+2) = 65,536 + 65,536 = 131,072 < 763,265

2^18 = 2^17*2 = 262,144 < 763,265

2^19 = 2^18 * 2 = 524,288 < 763,265

Therefore, 2^19 is the largest power of 2 that fits into 763,265

763,265 - 2^19 = 763,265 - 524,288 = 238,977

Ie, 763,265 = 2^19 + 238,977

By our previous work, the power we're looking for is greater than or equal to 17 and less than 18 since 2^18 > 238,977 and 2^17 < 238,977

therefore, 2^17 is the largest power of 2 that fits into 238,977

238,977 - 2^17 = 238,977 - 131,072 = 107,905

Ie, 763,265 = 2^19 + 2^17 + 107,905

By our work in doing the binary search for 19, the biggest power of 2 that can fit into 107,905 is less than 2^17 (since 2^17 > 107,905), and greater than or equal to 2^15 since 2^15 < 107,905

2^16 = 65,536 < 107,905, so 2^16 is the largest power of 2 that can git in 107,905

107,905 - 2^16 = 107,905 - 65,536 = 42,369

Therefore, 763,265 = 2^19 + 2^17 + 2^16 + 42,369

By the same technique, we see 2^15 is the largest power of 2 that fits into 42,369 is 2^15

42,369-2^15 = 42,369 - 32,768 = 9,601

Therefore, 763,265 = 2^19 + 2^17 + 2^16 + 2^15 + 9,601

2^15 = 32,768 > 9,601 and 2^10 = 1,024 < 9,601

2^12 = 2^10 * 2^2 = 2^10 * 4 = (1025 -1 ) * 4 = 4100 - 4 = 4,096 < 9,601

2^13 = 2^12 * 2 = 8,192 < 9,601

Therefore, 2^13 is the largest power of 2 that fits into 9,601

9,601 - 2^13 = 9,601 - 8,192 = 1,409

Therefore, 763,265 = 2^19 + 2^17 + 2^16 + 2^15 + 2^13 + 1,409

Do another binary search... 2^10 = 1,024 < 1,409, 2^12 = 8,192 > 1,409

2^11 = 2,048 > 1,409

Therefore, 2^10 is the largest power of 2 that fits into 1,409

1,409 - 2^10 = 1,409 - 1,024 = 385

Therefore, 763,265 = 2^19 + 2^17 + 2^16 + 2^15 + 2^13 + 2^10 + 385

Do a binary search for the biggest power of 2 that fits into 385:

2^10 = 1,024 > 385, 2^5 = 32 < 385 ==> exponent is >= 5, less than 10

2^7 = 4 * 2^5 = 128 < 385
2^8 = 2*128 = 256 < 385
2^9 = 512 > 385

Therefore, 2^8 is the largest power of 2 that fits into 385

385 - 2^8 = 385 - 256 = 129

Therefore, 763,265 = 2^19 + 2^17 + 2^16 + 2^15 + 2^13 + 2^10 + 2^8 + 129

129 = 128 + 1 = 2^7 + 1 = 2^7 + 2^0

Therfore, 763,265 = 2^19 + 2^17 + 2^16 + 2^15 + 2^13 + 2^10 + 2^8 + 2^7 + 1
763,265 = 2^16 * (2^3 + 2 + 1) + 2^8 *( 2^7 + 2^5 + 2^2 + 1) + 2^4 * 2^3 + 1

-----------------------------------------------------------------------------------

14^763265 mod 37 = 14^(2^16 * (2^3 + 2 + 1) + 2^8 *( 2^7 + 2^5 + 2^2 + 1) + 2^4 * 2^3 + 1) mod 37

= 14^(2^16 * (2^3 + 2 + 1)) * 14^(2^8 *( 2^7 + 2^5 + 2^2 + 1)) * 14^(2^7) * 14 mod 37

14 ^ 2 mod 37 = (10+4)*(10+4) mod 37 = (100 + 80 + 16) mod 37 = 100 mod 37 + 80 mod 37 + 16 mod 37 = 26 mod 37 + 6 mod 37 + 16 mod 37 = ( 32 + 16 ) mod 37 = 11

14^4 mod 37 = 11^2 mod 37 = 121 mod 37 = 10

14^8 mod 37 = 10^2 mod 37 = 100 mod 37 = 26

14^16 mod 37 = 26^2 mod 37 = ((20+6)*(20+6)) mod 37
= (400 + 240 + 36) mod 37 = 400 mod 37 + 240 mod 37 + 36 mod 37
= 30 mod 37 + 18 mod 37 + 36 mod 37
= (30 + 18 + 36) mod 37 = (30 + 17) mod 37 = 10

14^32 mod 37 = 10^2 mod 37 = 26

14^64 mod 37 = 26^2 mod 37 = 10

14^128 mod 37 = 10^2 mod 37 = 26

ie, 14 ^ (2^k) mod 37 = {10 if k even; 26 if k odd}

Since 763,265 = 2^19 + 2^17 + 2^16 + 2^15 + 2^13 + 2^10 + 2^8 + 2^7 + 1,

14^763,265 = 14 ^ (2^19 + 2^17 + 2^16 + 2^15 + 2^13 + 2^10 + 2^8 + 2^7 + 1)
= 14^(2^19) * 14^(2^17) * 14^(2^16) * 14 ^(2^15) * 14^(2^13) * 14^(2^10) * 14^(2^8) * 14^(2^7) * 14

Therefore, 14^763,265 mod 37 = 26 * 26 * 10 * 26 * 26 * 10 * 10 * 26 * 14 mod 37

26 * 26 * 10 * 26 * 26 * 10 * 10 * 26 * 14 mod 37
= (26 * 26) * 10 * 26 * 26 * 10 * 10 * 26 * 14 mod 37
= (10) * 10 * 26 * 26 * 10 * 10 * 26 * 14 mod 37
= (10 * 10) * 26 * 26 * 10 * 10 * 26 * 14 mod 37
= (26) * 26 * 26 * 10 * 10 * 26 * 14 mod 37
= (26* 26) * 26 * 10 * 10 * 26 * 14 mod 37
= (10) * 26 * (10 * 10) * 26 * 14 mod 37
= (10) * 26 * (26) * 26 * 14 mod 37
= (10) * (26*26) * 26 * 14 mod 37
= (10) * (10) * 26 * 14 mod 37
= (10*10) * 26 * 14 mod 37
= (26) * 26 * 14 mod 37
= (26*26) * 14 mod 37
= (10) * 14 mod 37
= (10*14) mod 37
= 140 mod 37

Therefore, 14^763265 mod 37 = 140 mod 37 = (37*3 + 29) mod 37 = 29

ie, the remainder of 14^763265 / 37 is 29

Hmmmmm...I worked it out using residues and got 8 (which is -29)...

763265=1+128+256+1024+8192+32768+65536+131072+5242 88

so 14^763265 = 14^(1+128+256+1024+8192+32768+65536+131072+524288)

14 mod 37 = -14
14^128 mod 37 = -11
14^256 mod 37 = 10
14^1024 mod 37 = 10
14^8192 mod 37 = -11
14^32768 mod 37 = -11
14^65536 mod 37 = 10
14^131072 mod 37 = -11
14^524288 mod 37 = -11

Therefore 14^763265 mod 37 = (-14)(-11)(10)(10)(-11)(-11)(10)(-11)(-11) mod 37 = 2254714000 mod 37 = 8

[spurster]

14^763265 mod 37

14^x mod 37 cycles every 12 values of x, e.g.,

14^0 mod 37 = 1
14^1 mod 37 = 14
14^2 mod 37 = 11
14^3 mod 37 = 6
14^4 mod 37 = 10
14^5 mod 37 = 29
14^6 mod 37 = 36
14^7 mod 37 = 23
14^8 mod 37 = 26
14^9 mod 37 = 31
14^10 mod 37 = 27
14^11 mod 37 = 8
14^12 mod 37 = 1 (back to 1 again)

Noting that 763265 mod 12 = 5, it follows

14^763265 mod 37 = 14^5 mod 37 = 29

[baseline bum]

Travis, you messed up on the first part... 14 mod 37 is 14, not -14... subs ute 14 for -14 or -23 for -14 and mod the product by 37 and you get 29

[scott]

Duh!!!

[travis2]

My first term may be in error. I took 14 mod 37 as -14...probably should be +14.

Flipping that first sign gives the answer as -8 rather than 8. And -8 and 29 are equivalent (mod 37)

BTW, spurster, an easy cycle occurs if you expand the exponent as a binary sum, as baseline and I did. As the exponents increase (2, 4, 8, 16, 32, 64...) the residues are (11, 10, -11, 10, -11, 10...)

[travis2]

Travis, you messed up on the first part... 14 mod 37 is 14, not -14... subs ute 14 for -14 or -23 for -14 and mod the product by 37 and you get 29

Yeah, I was typing as you were typing...you finished first...

[Spurminator]

That's impressive and all, but can you combine a binary equation with an elephant joke?

[travis2]

That's impressive and all, but can you combine a binary equation with an elephant joke?

Probably not and keep it clean...

[scott]

You guys should just splurge for Excel.

[baseline bum]

Yeah right... the opportunity cost of Excel is 212 gropes at the tip rail.

[scott]

[cherylsteele]

This is good and all....but can you balance my bank account?


You show that stuff to the teller and they would just look at you like a puzzled puppy or kitten......then still say you are $25.00 in the hole.