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]

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

How is it 2^15 + 1 ?

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search