# Number Theory: Finite (modular) arithmetics

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