1. ## natural number problem

Let A and B be two Natural Numbers. Suppose the remainder when A is divided by n is a and the remainder when B is divided by n is b. How does the remainder when A x B is divided by n compare to the remainders a and b? Can the remainder of A x B divided by n be determined by just considering a and b? If so, prove your theory.

Thanks!!

2. Originally Posted by kelly1183
Let A and B be two Natural Numbers. Suppose the remainder when A is divided by n is a and the remainder when B is divided by n is b. How does the remainder when A x B is divided by n compare to the remainders a and b? Can the remainder of A x B divided by n be determined by just considering a and b? If so, prove your theory.

Thanks!!
Symbolically,

$\displaystyle A \equiv a\ (\text{mod }n)$
$\displaystyle B \equiv b\ (\text{mod }n)$
$\displaystyle AB \equiv \ ?\ (\text{mod }n)$

The answer is known to be

$\displaystyle AB \equiv ab\ (\text{mod }n)$

To prove, just write

$\displaystyle A = k_1n + a$
$\displaystyle B = k_2n + b$

and expand the product $\displaystyle AB$.