Thread: abmod(2^n) == abdiv(2^n) if 2^n + 1 ??

Hi,

I am stuck with the following problem:

What is the result of (ab mod (2^n + 1)), if (ab mod (2^n)) = (ab div (2^n))? Is this case possible if a and b were whole numbers in the range of {1,2,...,2^n} and 2^n +1 was a prime number? Can you please explain the answer just a little bit?

2^n denotes 2 raised to the power of n.
ab div n means the quotient when ab is divided by n.

Thanks a lot in advance.

Originally Posted by zeeshanzia84

Hi,

I am stuck with the following problem:

What is the result of (ab mod (2^n + 1)), if (ab mod (2^n)) = (ab div (2^n))? Is this case possible if a and b were whole numbers in the range of {1,2,...,2^n} and 2^n +1 was a prime number? Can you please explain the answer just a little bit?

2^n denotes 2 raised to the power of n.
ab div n means the quotient when ab is divided by n.

Thanks a lot in advance.

You are saying quotient and remainder when ab is divided by 2^n are same. Lets call it r, then:

ab = (quotient)(2^n) + remainder => ab = r(2^n) + r = r(2^n + 1) => ab mod 2^n + 1 = 0