Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/