Skip to main content

Basic Modular Arithmetic

In simple terms, Modular Arithmetic calculates the remainder of anything divided by anything. The later is called modulus. e.g. ( 15 / 7 ) Quotient: 2, Remainder 1. 

In greater sense, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value—the modulus ( src: Wikipedia ).
Take a look at hour clock. After 12:59 pm, we say 1:00 pm, because we modulo the hours by 12. 13 pm % 12 is 1 pm. (%) represents modulus operator.
Examples: 5 % 2 = 1, 14458948 % 25 = 23

a≡b (mod n)
This says that a is congruent to b modulo n. It means both a and b has same remainder when divided by n. e.g. 38≡14 (mod 12)

Commonly Used Properties:
  • Reflexivity: a ≡ a (mod n)
  • Symmetry: a ≡ b (mod n) if and only if b ≡ a (mod n)
  • Transitivity: If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)
  • If a1 ≡ b1 (mod n) and a2 ≡ b2 (mod n), or if a ≡ b (mod n), then:a + k ≡ b + k (mod n) for any integer k (compatibility with translation)
  • k a ≡ k b (mod n) for any integer k (compatibility with scaling)
  • a1 + a2 ≡ b1 + b2 (mod n) (compatibility with addition)
  • a1 – a2 ≡ b1 – b2 (mod n) (compatibility with subtraction)
  • a1 a2 ≡ b1 b2 (mod n) (compatibility with multiplication)
  • ak ≡ bk (mod n) for any non-negative integer k (compatibility with exponentiation)
Simple C program to perform Modulo:

In CS, modular arithmetic is used in many algorithms where integers become too big to handle.

For more details:

 modulo C.

Comments

Popular posts from this blog

SPOJ - GSS1

Considering input series: { 4 , -10 , 3 , 100 , -20 , 1 } Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } A node contains-  [ START & END is a node's segment limit ] Prefix is the maximum sum starting at START, end can be anywhere. There are two possibilities of the maximum. One, node's leftChild's prefix or two, adding leftChild's sum + rightChild's prefix. (which will make the prefix contiguous) Suffix is the maximum sum ending at END, start can be anywhere. There's two possibility of the maximum. One, node's rightChild's already calculated suffix or two, add rightChild's sum + leftChild's suffix   (which will make the suffix contiguous). Sum : leftChild's sum + rightChild's sum. MAX Maximum of  -  prefix (result is in the node, starts from START but doesn't end in END ) suffix  (result is in the node, doesn't start from START but surely ends in END ) leftChild's max ( result is in left ...

Minimum moves for balancing brackets

You’re given a non-empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition of being stable is as follows: An empty string is stable. If S is stable, then {S} is also stable. If S and T are both stable, then ST (the concatenation of the two) is also stable. All of these strings are stable: {}, {}{}, and {{}{}}; But none of these: }{, {{}{, nor {}{. The only operation allowed on the string is to replace an opening brace with a closing brace, or visa-versa. Solution Heuristics: Traverse the string. When the number of opening braces( { ) matches the number of closing braces ( } ), the string is balanced. Else it's not balanced. So count both of them. Make a list. Insert only opening braces. If a closing brace is found delete one brace( if the size of the list is > 0 ) from the list. Because they would make a pair. If the list is empty then we'll conve...