Number Theory: Finite (modular) arithmetics

Understanding Finite (Modular) Arithmetic

Finite (Modular) arithmetic, also known as clock arithmetic, is a system of arithmetic for integers where numbers “wrap around” after they reach a certain value, the modulus.
The basic idea of finite arithmetic involves performing usual arithmetic, but at the end of the operation, the result is always taken modulo m, where m is the modulus.
The operation a mod m gives the remainder r after a is divided by m. This is represented as a ≡ r (mod m), meaning a and r are congruent modulo m.

In modular arithmetic, equivalence classes are used to cluster integers together. All integers in the same class are congruent to each other modulo m.
Modular arithmetic has the closure property. If a and b are integers and m is the modulus, then (a+b) mod m and (a.b) mod m both result in integers.
It also obeys commutativity, associativity, and distributivity. This means arithmetic operations can be rearranged without changing the result, similar to normal arithmetic.
However, regular division is not valid in modular arithmetic. It has a different definition namely multiplicative inverse which is more complex.

Finite arithmetic has numerous applications in computing, cryptography, and various branches of mathematics.
It is significantly used in public key cryptosystems, including RSA, a widely-used public-key cryptosystem for secure data transmission.
Modular arithmetic is vital in computing for efficient calculations and handling the overflow of numerical data.

Addition, subtraction and multiplication in finite arithmetic work the same as in ordinary arithmetic, but when you get your answer, you divide by the modulus and keep only the remainder.
Division in modular arithmetic involves finding an inverse. If you want to divide by a number, you instead multiply by its modular inverse.
The modular inverse of a modulo m is a number x such that ax ≡ 1 (mod m). If such an x exists, it can be found using the extended Euclidean algorithm.

Finite arithmetic is a cornerstone in the field of number theory. It offers a simplified framework for studying the properties of integers that makes it easier to prove theorems.
It forms the basis for Euler’s theorem and Fermat’s little theorem, two fundamental theorems in number theory.
The concept of congruence in finite arithmetic is pivotal in understanding number theoretic functions and modular forms.

In cryptography, modular arithmetic forms the basis for algorithms to create keys and encrypt messages in cryptosystems.
The RSA cryptosystem works on the principle of modular arithmetic, exploiting the difficulty of factoring large primes.
A firm understanding of finite arithmetic enables better comprehension of cryptographic algorithms and encryption techniques.