Multiplication of Integers Modulo (2^16 + 1)

Date: 10/18/2002 at 19:05:38
From: Sudha Joish
Subject: Multiplication of integers modulo (2^16 + 1)

Hi Dr Math,

I need to prove the following:

   2^16 * 2^15 mod (2^16 + 1) = 2^15 + 1

Consider LHS: 

   2^16 * 2^15 mod (2^16 + 1)
   = 2^31 mod (2^16 + 1)

   [2^16 + 1 is divisible in 2^31 once]

   = 2^15 [ is this what remains? am not sure about this...]

This is what I have been able to come up with. 

How is it 2^15 + 1 ?

Please help.

Thanks.
- Sudha

Date: 10/18/2002 at 19:25:16
From: Doctor Paul
Subject: Re: Multiplication of integers modulo (2^16 + 1)

Notice first that 2^16 = -1 mod (2^16 + 1)

Then 

   2^16 * 2^15 mod (2^16 + 1) = 

   -2^15 mod (2^16 + 1).

Now notice that

   -2^15 - (2^15 + 1) = -2^15 - 2^15 - 1 =

   -1 * (2^15 + 2^15 + 1) = -1 * (2*2^15 + 1) = 

   -1 * (2^16 + 1)

Clearly we know that 2^16 + 1 divides -1 * (2^16 + 1).

But

   -1 * (2^16 + 1) = -2^15 - (2^15 + 1)

Thus

   2^16 + 1 divides -2^15 - (2^15 + 1)

And this is equivalent to writing:

   -2^15 = (2^15 + 1) mod (2^16 + 1)

I hope this helps.  Please write back if you'd like to talk about 
this some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/