# 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.

## Properties of Modular Arithmetic

• 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.

## Applications of Modular Arithmetic

• 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.

## Solving Problems using Finite Arithmetic

• 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 and Number Theory

• 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.

## Finite Arithmetic and Cryptography

• 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.