SolitaryRoad.com

Website owner: James Miller

[ Home ] [ Up ] [ Info ] [ Mail ]

CONGRUENCE, RESIDUE CLASSES OF INTEGERS MODULO N

Congruence. Let n be a positive integer. We say two integers are congruent “modulo n" if they differ by an integral multiple of the integer n. For example, if n = 5 we can say that 3 is congruent to 23 modulo 5 (and write it as 3 23 modulo 5) since the integers 3 and 23 differ by 4x5 = 20. The statement a b (mod n) is equivalent to the statement “a - b is divisible by n” or the statement “there is an integer k for which a - b = kn”. The integer n is called the modulus of the congruence.

An alternate definition: a b (mod n) if and only if a and b have the same remainder when divided by n.

The modulus arithmetic concept occurs in everyday life in telling time. Clocks go up to12 and then start over, thus giving time modulus 12.

The congruence relation a b (mod n) creates a set of equivalence classes on the set of integers in which two integers are in the same class if they are congruent modulus n, i.e. if they leave the same remainder when divided by n.

Syn. Modulus, modulo, mod

Residue classes of integers mod n. The congruence relation a b (mod n) on the set of integers I separates the integers into n equivalence classes,

[0]_{n}, [1]_{n}, [2]_{n}, ... ,[n-1]_{n},

called* residue classes modulo n*. Each equivalence class [r]_{n} consists of all integers congruent to
r where r is one of the integers 0, 1, 2, ... ,n-1. These n integers 0, 1, 2, ... ,n-1 are called the
class representatives. Thus equivalence class [3]_{n} consists of all integers congruent to 3 mod n
where the integer 3 is the class representative.

Example. The residue classes of integers mod 4 are:

[0]_{4} = { ... , -16, -12, -8, -4, 0, 4, 8, 12, 16, ... }

[1]_{4} = { ... , -15, -11, -7, -3, 1, 5, 9, 13, 17, ... }

[2]_{4} = { ... , -14, -10, -6, -2, 2, 6, 10,14, 18, ... }

[3]_{4} = { ... , -13, -9, -5, -1, 3, 7, 11, 15, 19, ... }

I/(n), the set of all residue classes mod n. We denote the set of all residue classes modulo n by I/(n). For example,

I/(4) = { [0]_{4}, [1]_{4}, [2]_{4, }[3]_{4} }

and

I/(n) = { [0]_{n},, [1]_{n},, [2]_{n},, ... ,[n-1]_{n}, }

Note that I/(n) consists of a set of sets.

Modular arithmetic (or arithmetic modulo n). A modular arithmetic or arithmetic modulo n is obtained by using only the class representatives 0, 1, 2, ... ,n-1 and defining addition and multiplication by letting the sum a + b and the product ab be the remainder after division by n of the ordinary sum and product of a and b. E.g. if n = 7, then 2 + 6 1, 3∙6 4, and the multiplicative inverse of 2 is 4, since 2∙4 1. Multiplicative inverses need not exist, however. For example, if n = 15, then 3 has no multiplicative inverse, since a multiplicative inverse a would need to meet the condition that 3∙a - k∙15 = 1 or, equivalently, a - 5k = 1/3 for some set of integers a and k. But there are no set of integers a and k that will meet this condition.

Arithmetic modulo n is a commutative ring with unit element. If n is a prime, then arithmetic modulo n is a field.

References

Saunders, MacLane. A Survey of Modern Algebra. p. 23 - 29

Ayres. Modern Algebra. p.53

James & James. Mathematics Dictionary. “Congruence”

More from SolitaryRoad.com:

Jesus Christ and His Teachings

Way of enlightenment, wisdom, and understanding

America, a corrupt, depraved, shameless country

On integrity and the lack of it

The test of a person's Christianity is what he is

Ninety five percent of the problems that most people have come from personal foolishness

Liberalism, socialism and the modern welfare state

The desire to harm, a motivation for conduct

On Self-sufficient Country Living, Homesteading

Topically Arranged Proverbs, Precepts, Quotations. Common Sayings. Poor Richard's Almanac.

Theory on the Formation of Character

People are like radio tuners --- they pick out and listen to one wavelength and ignore the rest

Cause of Character Traits --- According to Aristotle

We are what we eat --- living under the discipline of a diet

Avoiding problems and trouble in life

Role of habit in formation of character

Personal attributes of the true Christian

What determines a person's character?

Love of God and love of virtue are closely united

Intellectual disparities among people and the power in good habits

Tools of Satan. Tactics and Tricks used by the Devil.

The Natural Way -- The Unnatural Way

Wisdom, Reason and Virtue are closely related

Knowledge is one thing, wisdom is another

My views on Christianity in America

The most important thing in life is understanding

We are all examples --- for good or for bad

Television --- spiritual poison

The Prime Mover that decides "What We Are"

Where do our outlooks, attitudes and values come from?

Sin is serious business. The punishment for it is real. Hell is real.

Self-imposed discipline and regimentation

Achieving happiness in life --- a matter of the right strategies

Self-control, self-restraint, self-discipline basic to so much in life

[ Home ] [ Up ] [ Info ] [ Mail ]