Modular Arithmetic💯✍️

Addition, subtraction and multiplication

 operation in mudulo in arithemetic modulo

Modular Arithmetic

Modular arithmetic is the arithmetic of congruences, occasionally referred informally as "clock arithmetic."

In modular arithmetic, numbers "wrap around" on reaching a specific fixed quantity, referred to as the modulus (which would be 12 with regards to hours on a clock,or 60 with regards to minutes or seconds on a clock.

It is normal and regular to denote the equivalence class [a] (under the equality relation (R) of a nonnegative integer a < n by a

For instance, in arithmetic modulo 12 (for which the linked ring is C12), the permissible numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and 11.

This arithmetic is occasionally known as "clock arithmetic" because the additive structure here is equivalent to that used to determine times for a twelve-hour clock, apart from the fact that 0 is frequently replaced, on a clock, by 12.

Example calculations in arithmetic modulo 12 are statements such as "11+1=0" or "7+8=3", or "5·7=11" even though the equal sign = is usually replaced with the congruence sign ≅ in statements like that to show that that there is an application of modular arithmetic.

More plainly still, a notation like the one below is constantly used.

11+1≅0(mod 12)

Arithmetic modulo 2 is occasionally known as "Boolean arithmetic", due to t that the ring C2 is the canonical instance of a Boolean ring.

The best way to understand modular arithmetic is to consider the face of a clock.

The numbers move from 1 to 12, but when you reach "13 o'clock", it in reality turns into 1 o'clock again (for instance, the way the 24 hour clock numbering goes).

Therefore, 13 turns into 1, 14 turns into 2, etc

This can go on moving, in order to allow you reach so when you get to "25 o'clock'', you are in reality back round to where 1 o'clock is on the clock face (and as well where 13 o'clock was too).

Thus in this clock world, you are just concerned about where you are in relation to the numbers 1 to 12. In this world, 1, 13, 25, 37, dots are all taken to be equivalent to e 2, 14, 26, 38, .

What we are talking about is "13=1+ a few multiple of 12", and "38=2+ a few multiple of 12", or, as an alternative, "the remainder when you divide 13 by 12 is 1" and "the remainder when you divide 38 by 12 is 2''.

Addition of congruences

We can add congruences.

For instance, 17 ≡ 4 mod 13, and 42 ≡ 3 mod 13, so 17+42 ≡ 4+3 ≡ 7 mod 13. Observe that both of the congruences that we're adding are mod n.

The same goes for the answer - we don't add the moduli. The same goes for multiplication but Division is a bit more tricky and should be treated cautious.

The example below will illustrate why. 10 ≡ 2 mod 8. Supposing we "divide both sides by 2", we would obtain 5 ≡ 1 mod 8, which doesn’t make any sense.

To obtain an actual congruence, we ought to divide the 8 by 2 also: 5 ≡ 1 mod 4 is fine. This is so because a ≡ b mod n means that a=b+k n for a few integer n.

But at this point, this is a normal equation, and if we're going to divide a by anything, then we have to divide everyone of the right-hand side by 2 in addition, including k n. Generally, it's best not to divide congruences; rather consider, what they actually mean (instead of making use of shorthand and compute from there.

Let's explore the multiplication characteristics of modular arithmetic:

(A * B) mod C = (A mod C * B mod C) mod C

Example for Multiplication:

Let A=4, B=7, C=6

Let's verify: (A * B) mod C = (A mod C * B mod C) mod C

LHS = Left Hand Side of the Equation

RHS = Right Hand Side of the Equation

LHS = (A * B) mod C

LHS = (4 * 7) mod 6

LHS = 28 mod 6

LHS = 4

RHS = (A mod C * B mod C) mod C

RHS = (4 mod 6 * 7 mod 6) mod 6

RHS = (4 * 1) mod 6

RHS = 4 mod 6

RHS = 4

LHS = RHS = 4

Proof for Modular Multiplication

Lets prove that (A * B) mod C = (A mod C * B mod C) mod C

From the quotient remainder theorem we could write A and B as:

A = C * Q1 + R1 where 0 ≤ R1 < C and Q1 is a few integer. A mod C = R1

B = C * Q2 + R2 where 0 ≤ R2 < C and Q2 is a few integer. B mod C = R2

LHS = (A * B) mod C

LHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C

LHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C

LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C

We can take away the multiples of C when we take the mod C

LHS = (R1 * R2) mod C

After that we will do the RHS

RHS = (A mod C * B mod C) mod C

RHS = (R1 * R2 ) mod C

Thus RHS = LHS

LHS = RHS = (R1 * R2 mod C)

A lot of composite cryptographic algorithms are in reality based on rather simple modular arithmetic. In modular arithmetic, the numbers we are working with are merely integers and the operations made use of are addition, subtraction, multiplication and division.

The only variation between modular arithmetic and the primary school arithmetic is that in modular arithmetic every operation is carried out with regard to a positive integer, i.e. the modulus.

A few basic concepts of modular arithmetic

The division theorem tells us that for two integers a and b where b ≠ 0, there is constantly specific integers q and r in a way that a = qb + r and 0 ≤ r < |b|. For instance, a = 17, b=3, we can find q = 5 and r = 2.

Therefore, 17 = 3*5+2. a is known as the dividend, b is known as the divisor, q is known as the quotient and r is known as the remainder. If r = 0, in that case, we say b divides a or a is divisible by b.

This forms a natural congruence relation on the integers. For a positive integer n, two integers a and b are said to be congruent modulo n (or a is congruent to b modulo n), if a and b have the same remainder when divided by n (or the same if a − b is divisible by n ). It can be expressed as a ≡ b mod n.

n is known as the modulus.

For instance:

Two odd numbers are congruent modulo 2 due to the fact that all odd numbers can be written as 2n+1;

Two even numbers are congruent modulo 2 due to the fact that every even number can be written as 2n+0;

38 ≡ 23 mod 15 due to the fact that 38 = 15*2 + 8 and 23 = 15 +8;

-1 ≡ 1 mod 2 as a result of the fact that -1 = -1*2+1 and 1 = 0*2+1;

8 ≡ 3 mod 5 as a result of the fact that 8 = 5+3 and 3 = 0*5+3;

-8 ≡ 2 mod 5 because -8 = -2*5+2 and 2 = 0*5+2;

8 ≢ -8 mod 5 as a result of the fact that 8 = 5+3 and -8 = -2*5+2. The remainders 3 and 2 are not the same.

You ought to be cautious with negative numbers. They are normally not congruent to their positive counter parts, just as you would notice in the instances given above.

Congruence is an equivalence relation, if a and b are congruent modulo n, then they do not have any variation in modular arithmetic under modulo n.

. Due to this, in modular n arithmetic we normally make use of just n numbers 0, 1, 2, ..., n-1. Every other number can be obtained congruent to one of the n numbers.

Therefore, the way to carryout arithmetic operations with moduli are as follows: Moduli operation for addition, subtraction and multiplication is a bit simple. Just compute it as you would do in ordinary arithmetic and reduce the result to the smallest positive remainder by dividing the modulus.

For istance:

12+9 ≡ 21 ≡ 1 mod 5

12-9 ≡ 3 mod 5

12+3 ≡ 15 ≡ 0 mod 5

15-23 ≡ -8 ≡ 2 mod 5

35*7 ≡ 245 ≡ 0 mod 5

-47*(5+1) ≡ -282 ≡ 3 mod 5

373 ≡ 50653 ≡ 3 mod 5 (exponentiation is merely a shorthand for repeated multiplication)

Occasionally, the calculation can be simplified due to the fact that for any integer a1, b1, a2 and b2, if we are aware that a1 ≅ b1 mod n and a2 ≅ b2 mod n then the following is always applicable:

a1+a2 ≅ b1+b2 mod n

a1-a2 ≅ b1-b2 mod n

a1*a2 ≅ b1*b2 mod n

For instance 35 ≅ 0 mod 5. Thus 35*7 ≅ 0*7 ≅ 0 mod 5. Also, 37 ≅ 2 mod 5 so 373 ≅ 23 ≅ 8 ≅ 3 mod 5.

Congruent operations with regards to division is not as simple as that due to the fact that division is not defined for every number. What that entails is that it is not always possible to carryout division in modular arithmetic.

First and foremost, as in ordinary arithmetic, division by zero is not defined. Therefore, 0 ought not to be the divisor. The tricky part is that the multiples of the modulus are congruent to 0.

For instance, 6, -6, 12, -12, ... are all congruent to 0 when the modulus is 6. Therefore not only 4/0 is not permissible, 4/12 is as well not permissible when the modulus is 6.

Secondly, moving back to the very fundamentals: what "division" mean in ordinary arithmetic is explained below. When we say 12 divided by 4 is equal to 3, we mean that there is a number 3 in such a way that 3*4 = 12.

Therefore division is defined through multiplication. But you experience problems when you extend this to modular arithmetic as is exemplified in the table below:

Multiplication modulo 6

* 1 2 3 4 5

1 1 2 3 4 5

2 2 4 0 2 4

3 3 0 3 0 3

4 4 2 0 4 2

5 5 4 3 2 1

Assuming that you are working in mod 6 and wish to compute 4/5, As we mentioned before, you in reality require to find x such that 5*x ≅ 4 mod 6.

From the table above, we can observe that 2 and only 2 satisfies this equation. That entails that 4/5 ≅ 2 mod 6. Now assuming, we want to calculate 4/2 ≅ ? mod 6. It appears easy due to 2*2 ≅ 4 mod 6.

Nevertheless, there is another possibility: 2*5 ≅ 4 mod 6. In this instance, division is not specifically defined, due to the fact that there are two numbers that can multiply by 2 to yield 4. In such situations, division is not permissible.

Topics you may be interested

•modular arithmetic

•amortization and depreciation

•arithmetic and geometry sequence

•approximation and significant figures

•annuties

•basic operation on number base

•instrument traded in capital market

•compound interest and percentage

•density distance time-and speed

•difference between bond debenture

•ratio proportions and rates

•positive and negative integers rational

•standard form numbers in standard form

•number bases conversion of numbers 

•modular arithmetic concept of modulo

•modular arithmetic applications in real

•identification of order notation

•fractions decimals and approximations