Modular arithmetic

related topics
{math, number, function}
{day, year, event}
{theory, work, human}
{album, band, music}
{acid, form, water}
{game, team, player}

In mathematics, modular arithmetic (sometimes called clock arithmetic) is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus.

The Swiss mathematician Leonhard Euler pioneered the modern approach to congruence in about 1750, when he explicitly introduced the idea of congruence modulo a number N.

Modular arithmetic was further advanced by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12 hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00. Usual addition would suggest that the later time should be 7 + 8 = 15, but this is not the answer because clock time "wraps around" every 12 hours; there is no "15 o'clock". Likewise, if the clock starts at 12:00 (noon) and 21 hours elapse, then the time will be 9:00 the next day, rather than 33:00. Since the hour number starts over after it reaches 12, this is arithmetic modulo 12.[1]

Contents

Congruence relation

Modular arithmetic can be handled mathematically by introducing a congruence relation on the integers that is compatible with the operations of the ring of integers: addition, subtraction, and multiplication. For a positive integer n, two integers a and b are said to be congruent modulo n, written:

if their difference a − b is an integer multiple of n. The number n is called the modulus of the congruence.

For example,

because 38 − 14 = 24, which is a multiple of 12.

For positive n and non-negative a and b, congruence of a and b can also be thought of as asserting that these two numbers have the same remainder after dividing by the modulus n. So,

because both numbers, when divided by 12, have the same remainder (2). Equivalently, the fractional parts of doing a full division of each of the numbers by 12 are the same: 0.1666... (38/12 = 3.1666..., 2/12 = 0.1666...). From the prior definition we also see that their difference, a − b = 36, is a whole number (integer) multiple of 12 (n = 12, 36/12 = 3).

Full article ▸

related documents
Filter (mathematics)
Semigroup
Countable set
Exclusive or
Homological algebra
XPath 1.0
Complex analysis
Scope (programming)
Ultrafilter
Key size
Partition (number theory)
Tychonoff's theorem
Absolute convergence
Galois theory
Ordinary differential equation
Natural transformation
Gaussian quadrature
Sequence
Normed vector space
Elliptic curve
IEEE 754-1985
Ideal class group
Database normalization
Holomorphic function
Linear combination
Algebraic structure
J (programming language)
E (mathematical constant)
Power series
Objective Caml