# remainder problem

• Jul 20th 2009, 08:35 AM
jashansinghal
remainder problem
what is the remainder in the given problem
$\frac{2^{1990}}{1990}$
• Jul 20th 2009, 11:33 AM
newtoinequality
.
• Jul 20th 2009, 09:24 PM
aidan
Quote:

Originally Posted by jashansinghal
what is the remainder in the given problem
$\frac{2^{1990}}{1990}$

$\frac{2^{1990}}{1990}$ is equivalent to $2^{1990}$ mod 1990

and
$1990_{10} \, = \, 11111000110_2$

Using the exponentiation algorithm mod 1990 at each step.

Spoiler:
1024
• Jul 21st 2009, 09:25 AM
jashansinghal
i dont know what is mod and how do we solve it
can u give step by step method
• Jul 22nd 2009, 10:15 AM
aidan
Quote:

Originally Posted by jashansinghal
i dont know what is mod and how do we solve it
can u give step by step method

There are hundreds of essays on the subject far better than anything I could do.
For the Exponentiaion Algorithm or Russian Peasant Algorithm, Russian Peasant Multiplication also check Google.
(NOTE: Lee Lady, professor Hawaii University, has some excellent essays.)

You need to be careful as you interpret the following note.
The base you are working with is the number 2: as in 2^1990
It is very easy to mistake the base 2 with the binary exponent value.
If your problem were 3^1990, the following would be much more clear.
][
the binary representation of decimal 1990 is: 11111000110
Code:

 10 9 8 7 6 5 4 3 2 1 0 <-exponent value  1 1 1 1 1 0 0 0 1 1 0 <-bit value
$2^0$ = 1 x 0 = 0
$2^1$ = 2 x 1 = 2 !
$2^2$ = 4 x 1 = 4 !
$2^3$ = 8 x 0 = 0
$2^4$ = 16 x 0 = 0
$2^5$ = 32 x 0 = 0
$2^6$ = 64 x 1 = 64 !
$2^7$ = 128 x 1 = 128 !
$2^8$ = 256 x 1 = 256 !
$2^9$ = 512 x 1 = 512 !
$2^{10}$=1024 x 1 = 1024 !
-----------------======
the sum..........= 1990
Take note of the exclamation marks.
(see positional notation, number systems, binary, decimal)

$2^2$ = 4
$2^2 mod (1990)$ = 4

$2^4$ = 16
$2^4 mod (1990)$ = 16

$2^8$ = 256
$2^8 mod (1990)$ = 256

$2^{16}$ = 65536
$2^{16} mod (1990)$ = 1856
Here's how:
$\frac{65536}{1990} \, = \, 32.93266332$
using only the integer part of the division or 32.

65536 - 32 x 1990 = 1856. 1856 is the remainder.
thus
$2^{16} mod (1990)$ = 1856

$2^{32}$ = 4294967296

$\frac{4294967296}{1990} = 2158275.023$

ignore decimal part
4294967296 - 2158275 * 1990 = 46
$2^{32} mod (1990)$ = 46
:::
Now, the short cut:
-----------------------
This should be obvious: $2^{32} = (2^{16})^2$
-----------------------
$2^{16} mod (1990)$ = 1856 (from above)
1856 x 1856 = 3444736

$\frac{3444736}{1990} = 1731.023116$

3444736 - 1731 x 1990 = 46
restated:
$2^{32} mod (1990) \equiv (2^{16})^2 mod (1990) \equiv 1856^2 mod (1990) \equiv 46$

$2^{64} mod (1990) \equiv (2^{32})^2 mod (1990) \equiv 46^2 mod (1990) \equiv 126$
(46x46 = 2116; 2116 - 1990 = 126)

$2^{128} mod (1990) \equiv 126^2 mod (1990) \equiv 1946$
the math (126^2 = 15876; 15876 - 1990 x 7 = 1946)

$2^{256} \, mod \, (1990) \, \equiv \, 1946^2 \, mod \, (1990) \equiv$ 3786916; 3786916 - 1902 x 1990 = 1936

$2^{512} \, mod \, (1990) \, \equiv \, 1936^2 \, mod \, (1990) \equiv$3748096; 3748096 - 1883 x 1990 = 926

$2^{1024} \, mod \, (1990) \equiv 926^2 \, mod \, (1990) \, \equiv \, 857476$; 857476 - 430 x 1990 = 1776

synopsis:
ALL values mod 1990
$2^2$ = 4
$2^4$ = 16
$2^{64}$ = 126
$2^{128}$ = 1946
$2^{256}$ = 1936
$2^{512}$ = 926
$2^{1024}$ = 1776

You need the product of those residues (1776 x 926 x 1936 x 1946 x 126 x 16 x 4) mod 1990.

(1776 x 926 ) mod 1990 = 836
(836 x 1936 ) mod 1990 = 626
(626 x 1946 ) mod 1990 = 316
(316 x 126 ) mod 1990 = 16
( 16 x 16 ) mod 1990 = 256
(256 x 4 ) mod 1990 = 1024

$2^{1990} \, = \,$

11212213821037641838211261730250800625217946309459
91406716447985181412364640986634625644029605963154
21723238734276119411469445211021782747209563609000
64972513586913002471902343817263588695316881975481
15137338732859195463512171761366673017832426429237
99711910701330467586859989849241515282750160373017
90300912516495018013525937732371563272857314544411
76762001979655338142876191485666369934489856131673
01959569331441814577169706892972697421731624269082
89983779501164116695096053678910074226753634436580
34720511968591074370394031117377266157313625740076
97876147886258594553557393376919388439633643700224

that number divided by 1990 will have a remainder of 1024.