CSE 141: Modular Arithmatic and Congruences

Definition:

1. If m|a-b then a \equiv b \pmod{m}.

Where a and b are integers and m is a positive integer.

2. If a\,\bmod\,m=r

and b\,\bmod\,m=r

then a \equiv b \pmod{m}.

Where a and b are integers and m is a positive integer.

3. If a=b+km

then, a \equiv b \pmod{m}.

Where a, b and k are integers and m is a positive integer.

Example:

5\,\bmod\,7=5

12\,\bmod\,7=5

So 12 \equiv 5 \pmod{7}

Algebra of Congruence:

If a \equiv b \pmod{m}

and c \equiv d \pmod{m}

then a+c \equiv b+d \pmod{m}

also ac \equiv bd \pmod{m}.

Advertisements

About f.nasim

A CS undergrad from Bangladesh.
This entry was posted in computer science, discrete mathematics, number theory and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s